COMPLETE GRAPH

In the mathematical field of graph theory, a 'complete graph' is a simple graph where an edge connects every pair of distinct vertices. 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.
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.
An important property of the complete graph is the quadratic number of connections. That is, the number of edges is a quadratic function of the number of nodes. As such, a complete graph can be the worst case for 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$

Contents

External links

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

★