Complete graph

Complete graph
K7, a complete graph with 7 vertices
Vertices	n
Edges	$\textstyle\frac{n (n-1)}{2}$
Radius	$\left\{\begin{array}{ll}0 & n = 1\\ 1 & \text{otherwise}\end{array}\right.$
Diameter	$\left\{\begin{array}{ll}0 & n = 1\\ 1 & \text{otherwise}\end{array}\right.$
Girth	$\left\{\begin{array}{ll}\infty & n \le 2\\ 3 & \text{otherwise}\end{array}\right.$
Automorphisms	n! (Sn)
Chromatic number	n
Chromatic index	n if n is odd n − 1 if n is even
Spectrum	$\left\{\begin{array}{ll}\{0^1\} & n = 1\\ \{(n - 1)^1, -1^{n - 1}\} & \text{otherwise}\end{array}\right.$
Properties	(n − 1)-regular Symmetric graph Vertex-transitive Edge-transitive Strongly regular Integral
Notation	Kn

In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.

A drawing of a compete graph, with its vertices placed on a regular polygon, is sometimes referred to as a mystic rose.

Properties

The complete graph on n vertices has n(n − 1)/2 edges (a triangular number), and is denoted by K_n (from the German komplett). It is a regular graph of degree n − 1. All complete graphs are their own maximal cliques. They are maximally connected as the only vertex cut which disconnects the graph is the complete set of vertices. The complement graph of a complete graph is an empty graph.

If the edges of a complete graph are each given an orientation, the resulting directed graph is called a tournament.

Geometry and topology

A complete graph with n nodes represents the edges of an (n − 1)-simplex. Geometrically K₃ forms the edge set of a triangle, K₄ a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K₇ as its skeleton. Every neighborly polytope in four or more dimensions also has a complete skeleton.

K₁ through K₄ are all planar graphs. However, every planar drawing of a complete graph with five or more vertices must contain a crossing, and the nonplanar complete graph K₅ plays a key role in the characterizations of planar graphs: by Kuratowski's theorem, a graph is planar if and only if it contains neither K₅ nor the complete bipartite graph K_3,3 as a subdivision, and by Wagner's theorem the same result holds for graph minors in place of subdivisions. As part of the Petersen family, K₆ plays a similar role as one of the forbidden minors for linkless embedding. In other words, and as Conway and Gordon proved, every embedding of K₆ is intrinsically linked, with at least one pair of linked triangles. Conway and Gordon also showed that any embedding of K₇ contains a knotted Hamiltonian cycle.

Examples

Complete graphs on n vertices, for n between 1 and 12, 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	K12: 66

External links

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