Complete graph

From Wikipedia, the free encyclopedia

Complete graph
K₇, a complete graph with 7 vertices
Vertices	n
Edges	n(n − 1) / 2
Automorphisms	n!
This box: view • talk • edit

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-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: