Complete graph
From Wikipedia, the free encyclopedia
| Complete graph | |
|---|---|
 K7, a complete graph with 7 vertices |
|
| Vertices | n |
| Edges | n(n − 1) / 2 |
| Diameter | 1 |
| Girth | 3 if n ≥ 3 |
| Automorphisms | n! (Sn) |
| Chromatic number | n |
| Chromatic index | n if n is odd n-1 if n is even |
| Properties | (n-1)-regular Symmetric graph Vertex-transitive Edge-transitive Unit distance Strongly regular Integral |
| Notation | Kn |
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 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.
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 11, are shown below along with the numbers of edges:
| K1:0 | K2:1 | K3:3 | K4:6 |
|---|---|---|---|
 |
 |
 |
 |
| K5:10 | K6:15 | K7:21 | K8:28 |
 |
 |
|
 |
| K9:36 | K10:45 | K11:55 | |
 |
 |
 |
[edit] See also
[edit] References
- ^ David Gries and Fred B. Schneider, A Logical Approach to Discrete Math, Springer, 1993, p 436.
[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
- Weisstein, Eric W., "Complete Graph" from MathWorld.
