Complete graph
From Wikipedia, the free encyclopedia
| Complete graph | |
 K7, a complete graph with 7 vertices |
|
| Vertices | n |
|---|---|
| Edges | n(n − 1) / 2 |
| Automorphisms | n! |
| Chromatic number | n |
| Properties | (n-1)-regular Vertex-transitive Edge-transitive Unit distance Strongly regular |
| Notation | Kn |
In 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 Kn. 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 K3 relates to a triangle, K4 a tetrahedron, K5 a pentachoron, etc.
K1 through K4 are all planar. Kuratowski's theorem says that a planar graph cannot contain K5 (or the complete bipartite graph K3,3) as a minor. Since Kn includes Kn − 1, no complete graph Kn 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 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:
| K1:0 | K2:1 | K3:3 | K4:6 |
|---|---|---|---|
 |
 |
 |
 |
| K5:10 | K6:15 | K7:21 | K8:28 |
 |
 |
|
 |
[edit] See also
[edit] External links
 |
Look up complete graph in Wiktionary, the free dictionary. |
- 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
- Weistein, Eric W., "Complete Graph" from MathWorld.
