TOPICS
Search

Complete Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
CompleteGraphs

A complete graph is a graph in which each pair of graph vertices is connected by an edge. The complete graph with n graph vertices is denoted K_n and has (n; 2)=n(n-1)/2 (the triangular numbers) undirected edges, where (n; k) is a binomial coefficient. In older literature, complete graphs are sometimes called universal graphs.

The complete graph K_n is also the complete n-partite graph K_(n×1)=K_(1,...,1_()_(n)).

The complete graph on n 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.

In the 1890s, Walecki showed that complete graphs K_n admit a Hamilton decomposition for odd n, and decompositions into Hamiltonian cycles plus a perfect matching for even n (Lucas 1892, Bryant 2007, Alspach 2008). Alspach et al. (1990) give a construction for Hamilton decompositions of all K_n.

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

K_n has graph genus [(n-3)(n-4)/12] for n>=3 (Ringel and Youngs 1968; Harary 1994, p. 118), where [x] is the ceiling function.

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

A=J-I.
(1)

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

K_3 is the cycle graph C_3, as well as the odd graph O_2 (Skiena 1990, p. 162). K_4 is the tetrahedral graph, as well as the wheel graph W_4, and is also a planar graph. K_5 is nonplanar, and is sometimes known as the pentatope graph or Kuratowski graph. Conway and Gordon (1983) proved that every embedding of K_6 is intrinsically linked with at least one pair of linked triangles, and K_6 is also a Cayley graph. Conway and Gordon (1983) also showed that any embedding of K_7 contains a knotted Hamiltonian cycle.

CompleteGraphMinimalEmbeddings

The complete graph K_n is planar for n=1, 2, 3, and 4. For n=5, 6, and 7, is it nonplanar with graph crossing number equal to its rectilinear crossing number. Guy's conjecture posits a closed form for the graph crossing number of K_n, which first differs from the rectilinear crossing number for K_8, where rcn=19 but cn=18. Minimal crossing embeddings are illustrated above, with minimal rectilinear and unrestricted (allowing curved edges) minimal embeddings shown for K_8 (Harary and Hill 1962-1963).

The complete graph K_n is the line graph of the star graph S_(n+1).

The chromatic polynomial pi_n(z) of K_n is given by the falling factorial (z)_n. The independence polynomial is given by

I_n(x)=1+nx,
(2)

and the matching polynomial by

mu(x)=He_n(x)
(3)
=2^(-n/2)H_n(x/(sqrt(2))),
(4)

where He_n(x) is a normalized version of the Hermite polynomial H_n(x).

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

CompleteGraphCycles

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

C_n=sum_(k=3)^(n)1/2(n; k)(k-1)!
(5)
=1/4n[2_3F_1(1,1,1-n;2;-1)-n-1],
(6)

where (n; k) is a binomial coefficient and _3F_1(a,b,c;d;z) 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, ..., n-1 graph edges can always be packed into K_n. 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 K_n is the crown graph K_2 square K_n^_.

See also

Barbell Graph, Clique, Complete Bipartite Graph, Complete Digraph, Complete k-Partite Graph, Empty Graph, Graph Complement, Guy's Conjecture, Lollipop Graph, Odd Graph, Regular Polygon Division by Diagonals, Singleton Graph Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Alikhani, S. and Ghanbari, N. "Golden Ratio in Graph Theory: A Survey." 9 Jul 2024. https://arxiv.org/abs/2407.15860.Alspach, B.; Bermond, J.-C.; and Sotteau, D. "Decomposition Into Cycles. I. Hamilton Decompositions." In Proceedings of the NATO Advanced Research Workshop on Cycles and Rays: Basic Structures in Finite and Infinite Graphs held in Montreal, Quebec, May 3-9, 1987 (Ed. G. Hahn, G. Sabidussi, and R. E. Woodrow). Dordrecht, Holland: Kluwer, pp. 9-18, 1990.Alspach, B. "The Wonderful Walecki Construction." Bull. Inst. Combin. Appl. 52, 7-20, 2008.Bryant, D. E. "Cycle Decompositions of Complete Graphs." In Surveys in Combinatorics 2007 (Eds. A. J. W. Hilton and J. M. Talbot). Cambridge, England: Cambridge University Press, 2007.Char, J. P. "Master Circuit Matrix." Proc. IEE 115, 762-770, 1968.Chartrand, G. Introductory Graph Theory. New York: Dover, pp. 29-30, 1985.Conway, J. H. and Gordon, C. M. "Knots and Links in Spatial Graphs." J. Graph Th. 7, 445-453, 1983.DistanceRegular.org. "Symplectic 7-Cover of K_9." https://www.math.mun.ca/distanceregular/graphs//symplectic7coverk9.html.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Harary, F. and Hill, A. "On the Number of Crossings in a Complete Graph." Proc. Edin. Math. Soc. 13, 333-338, 1962-1963.Holroyd, F. C. and Wingate, W. J. G. "Cycles in the Complement of a Tree or Other Graph." Disc. Math. 55, 267-282, 1985.Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 60-63, 1985.Lucas, É. Récréations Mathématiques, tome II. Paris, 1892.Ringel, G. and Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 12, 1986.Skiena, S. "Complete Graphs." §4.2.1 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 82, 140-141, and 162, 1990.Sloane, N. J. A. Sequence A002807/M4420 in "The On-Line Encyclopedia of Integer Sequences."Zaks, S. and Liu, C. L. "Decomposition of Graphs into Trees." In Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, LA, 1977 (Ed. F. Hoffman, L. Lesniak-Foster, D. McCarthy, R. C. Mullin, K. B. Reid, and R. G. Stanton). Congr. Numer. 19, 643-654, 1977.

Referenced on Wolfram|Alpha

Complete Graph

Cite this as:

Weisstein, Eric W. "Complete Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CompleteGraph.html

Subject classifications