Complete graph

related topics
{math, number, function}
{line, north, south}
{theory, work, human}

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(n-1)/2 edges, and is denoted by Kn (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 (n-1)-simplex. Geometrically K3 forms the edge set of a triangle, K4 a tetrahedron, etc. The Császár polyhedron, a nonconvex polyhedron with the topology of a torus, has the complete graph K7 as its skeleton. Every neighborly polytope in four or more dimensions also has a complete skeleton.

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 graph K3,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.[2]

Examples

Complete graphs on n vertices, for n between 1 and 12, are shown below along with the numbers of edges:

Full article ▸

related documents
Minkowski's theorem
Special functions
Bernoulli's inequality
NP-equivalent
Automorphism
Null set
Field of fractions
Algebraic closure
Noetherian ring
Irreducible fraction
Euler number
Hyperplane
Urysohn's lemma
Discrete probability distribution
Sum rule in integration
Equation
Cipher
Entire function
Ceva's theorem
Inverse transform sampling
Disjunctive normal form
Rational root theorem
Klein four-group
Exponential time
Unification
Euler's identity
Unit interval
Unitary matrix
Axiom of power set
Injective function