Get Complete Graph essential facts below. View Videos or join the Complete Graph discussion. Add Complete Graph to your PopFlock.com topic list for future reference or share this resource on social media.
The complete graph on vertices is denoted by . Some sources claim that the letter in this notation stands for the German word komplett, but the German name for a complete graph, vollständiger Graph, does not contain the letter , and other sources state that the notation honors the contributions of Kazimierz Kuratowski to graph theory.
can be decomposed into trees such that has vertices. Ringel's conjecture asks if the complete graph can be decomposed into copies of any tree with edges. This is known to be true for sufficiently large .
The number of all distinct paths between a specific pair of vertices in is given by
K1 through K4 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 K5 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 K5 nor the complete bipartite graphK3,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, K6 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 K6 into three-dimensional space is intrinsically linked, with at least one pair of linked triangles. Conway and Gordon also showed that any three-dimensional embedding of K7 contains a Hamiltonian cycle that is embedded in space as a nontrivial knot.
Complete graphs on vertices, for between 1 and 12, are shown below along with the numbers of edges: