In the mathematical field of graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge.
Contents
Properties
The complete graph on n vertices has n(n1)/2 edges, and is denoted by K_{n} (from the German komplett^{[1]}). It is a regular graph of degree n − 1. All complete graphs are their own 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.
Geometry and topology
A complete graph with n nodes represents the edges of an (n1)simplex. Geometrically K_{3} forms the edge set of a triangle, K_{4} a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K_{7} as its skeleton. Every neighborly polytope in four or more dimensions also has a complete skeleton.
K_{1} through K_{4} 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_{5} 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_{5} 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_{6} plays a similar role as one of the forbidden minors for linkless embedding.^{[2]}
Examples
Complete graphs on n vertices, for n between 1 and 12, are shown below along with the numbers of edges:
Full article ▸
