Complete graph

In the mathematical field of graph theory, a complete graph is a simple graph in which every pair of distinct vertices is connected by an edge. The complete graph on $n$ vertices has $n$ vertices and $n(n-1)/2$ edges, and is denoted by $K\_n$. 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.

A complete graph with n-nodes represents the edges of an (n-1)-simplex. Geometrically $K\_3$ relates to a triangle, $K\_4$ a tetrahedron, $K\_5$ a pentachoron, etc.

$K\_1$ through $K\_4$ are all planar. Kuratowski's theorem says that a planar graph cannot contain $K\_5$ (or the complete bipartite graph $K\_\{3,3\}$) as a minor. Since $K\_n$ includes $K\_\{n-1\}$, no complete graph $K\_n$ with $n$ greater than or equal to 5 is planar.

Since a complete graph contains all $n(n-1)/2$ possible edges, it gives a quadratic worst-case upper bound on the number of connections in large connected systems like social and computer networks.

Complete graphs on $n$ vertices, for $n$ between 1 and 8, are shown below along with the numbers of connections:

$K\_1:\; 0$	$K\_2:\; 1$	$K\_3:\; 3$	$K\_4:\; 6$
$K\_5:\; 10$	$K\_6:\; 15$	$K\_7:\; 21$	$K\_8:\; 28$

See also

• Cycle graph
• Path graph
• Null graph
• Clique (graph theory)

External links

• Counting Paths and Cycles in Complete Graphs. Results are available Mehdi Hassani, Cycles in graphs and derangements, Math. Gaz. 88(March 2004) pp. 123-126 (reprint) or here