Complete graph
From Wikipedia, the free encyclopedia
In the mathematical field of graph theory, a complete graph is a simple graph where an edge connects every pair of vertices. 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-simplex. Geometrically K3 relates to a triangle, K4 a tetrahedron, K5 a pentachoron, etc.
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.
Complete graphs on n vertices, for n between 1 and 8, are shown below:
 K1 |
 K2 |
 K3 |
 K4 |
 K5 |
 K6 |
 K7 |
 K8 |
[edit] External links
- Eric W. Weisstein, Complete Graph at MathWorld.
