Complete Graph

A complete graph is a simple graph in which each pair of distinct vertices is joined by an edge. The complete graph with graph vertices is denoted and has (the triangular numbers) undirected edges, where is a binomial coefficient. In older literature, complete graphs are sometimes called universal graphs.

The animation above constructs by joining each vertex to every higher-numbered vertex in turn, so each edge is drawn once. The colors identify the lower-numbered vertex of each edge (Eeanimation).

The complete graph is also the complete n-partite graph .

The complete graph on nodes is implemented in the Wolfram Language as CompleteGraph[n]. Precomputed properties are available using GraphData[{"Complete", n}]. A graph may be tested to see if it is complete in the Wolfram Language using the function CompleteGraphQ[g].

The complete graph on 0 nodes is a trivial graph known as the null graph, while the complete graph on 1 node is a trivial graph known as the singleton graph.

Walecki's construction gives a Hamilton decomposition of for odd , and a decomposition into Hamiltonian cycles plus a perfect matching for even (Lucas 1892, Alspach et al. 1990, Bryant 2007, Alspach 2008).

The graph complement of the complete graph is the empty graph on vertices. The simplex graph of is the hypercube graph (Alikhani and Ghanbari 2024).

has graph genus for (Ringel and Youngs 1968; Harary 1994, p. 118), where is the ceiling function.

The Klein bottle crossing number of is 0 for . Koman (1969) proved that the corresponding values for , , and are 1, 4, and 9, respectively.

The adjacency matrix of the complete graph takes the particularly simple form of all 1s with 0s on the diagonal, i.e., the unit matrix minus the identity matrix,

(1)

The complete graphs are distance-regular, geometric, and dominating unique.

is the cycle graph , as well as the odd graph (Skiena 1990, p. 162). is the tetrahedral graph, as well as the wheel graph , and is also a planar graph. is nonplanar, and is sometimes known as the pentatope graph or Kuratowski graph. Conway and Gordon (1983) proved that is intrinsically linked: every embedding in three-dimensional Euclidean space contains a pair of linked triangles. The graph is also a Cayley graph. Conway and Gordon (1983) also showed that any embedding of in three-dimensional Euclidean space contains a knotted Hamiltonian cycle.

The complete graph is planar for , 2, 3, and 4. For , 6, and 7, it is nonplanar with graph crossing number equal to its rectilinear crossing number. Harary-Hill conjecture posits a closed form for the graph crossing number of , which first differs from the rectilinear crossing number for , where but . Thus is a curvy graph but not a minimally curvy graph, since it contains the smaller curvy 16-cell graph as a proper subgraph. The illustrations above show a straight-line drawing of with 19 crossings and a drawing with curved edges and 18 crossings (Harary and Hill 1962-1963).

The complete graph is the line graph of the star graph .

The chromatic polynomial of is given by the falling factorial . The independence polynomial is given by

(2)

and the matching polynomial by

			(3)
			(4)

where is a normalized version of the Hermite polynomial .

The chromatic number and clique number of are . The automorphism group of the complete graph is the symmetric group (Holton and Sheehan 1993, p. 27).

The numbers of graph cycles in the complete graph for , 4, ... are 1, 7, 37, 197, 1172, 8018, ... (OEIS A002807). These numbers are given analytically by

			(5)
			(6)

where is a binomial coefficient and is a generalized hypergeometric function (Char 1968, Holroyd and Wingate 1985).

Complete graphs are geodetic.

It is not known in general if a set of trees with 1, 2, ..., graph edges can always be packed into . However, if the choice of trees is restricted to either the path or star from each family, then the packing can always be done (Zaks and Liu 1977, Honsberger 1985).

The bipartite double graph of the complete graph is the crown graph .