Complete graph

Complete graph
K7, a complete graph with 7 vertices
Vertices	n
Edges	n(n − 1) / 2
Diameter	1
Girth	3 if n ≥ 3
Automorphisms	n! (Sn)
Chromatic number	n
Chromatic index	n if n is odd n-1 if n is even
Properties	(n-1)-regular Symmetric graph Vertex-transitive Edge-transitive Unit distance Strongly regular Integral
Notation	Kn
This box: view • talk

In the mathematical field of graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on n vertices has n vertices and n(n-1)/2 edges, and is denoted by K_n (from the German komplett^[1]). It is a regular graph of degree n − 1. 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 complete graph with n nodes represents the edges of an (n-1)-simplex. Geometrically K₃ relates to a triangle, K₄ a tetrahedron, K₅ a pentachoron, etc.

K₁ through K₄ are all planar. Kuratowski's theorem says that a planar graph cannot contain K₅ (or the complete bipartite graph K_3,3) as a minor. Since K_n includes K_{n − 1}, no complete graph K_n with n greater than or equal to 5 is planar.

Since a complete graph contains all n(n-1)/2 possible edges, it gives a quadratic upper bound on the number of connections in large connected systems like social and computer networks.

Complete graphs on n vertices, for n between 1 and 11, are shown below along with the numbers of edges:

K1:0	K2:1	K3:3	K4:6
K5:10	K6:15	K7:21	K8:28
K9:36	K10:45	K11:55

See also

• Cycle graph
• Path graph
• Null graph
• Clique (graph theory)

References

External links

Look up complete graph in Wiktionary, the free dictionary.

• Counting Paths and Cycles in Complete Graphs. Results are available Mehdi Hassani, Cycles in graphs and derangements, Math. Gaz. 88(March 2004) pp. 123-126 (reprint) or here

• Weisstein, Eric W., "Complete Graph" from MathWorld.