Complete graph
|
|
In the mathematical field of graph theory a complete graph is a simple graph where an edge connects every pair of vertices. The complete graph on <math>n<math> vertices has <math>n<math> vertices and <math>n(n-1)/2<math> edges, and is denoted by <math>K_n<math>. It is a regular graph of degree <math>n-1<math>. All complete graphs are their own cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. A planar graph cannot contain <math>K_5<math> (or the complete bipartite graph <math>K_{3,3}<math>) as a minor.
Complete graphs on <math>n<math> vertices, for <math>n<math> between 1 and 8, are shown below:
Missing image
Complete_graph_K1.png
Complete_graph_K1.png
K1
Missing image
Complete_graph_K2.png
Complete_graph_K2.png
K2
Missing image
Complete_graph_K3.png
Complete_graph_K3.png
K3
Missing image
Complete_graph_K4.png
Complete_graph_K4.png
K4
Missing image
Complete_graph_K5.png
Complete_graph_K5.png
K5
Missing image
Complete_graph_K6.png
Complete_graph_K6.png
K6
Missing image
Complete_graph_K7.png
Complete_graph_K7.png
K7
Missing image
Complete_graph_K8.png
Complete_graph_K8.png
K8