Complete Graph - Geometry and Topology

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.