|
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 vertices has vertices and edges, and is denoted by . It is a regular graph of degree . 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 relates to a triangle, a tetrahedron, a pentachoron, etc. Kuratowski's theorem says that a planar graph cannot contain (or the complete bipartite graph ) as a minor. Since includes , no complete graph with greater than or equal to 5 is planar. Complete graphs on vertices, for between 1 and 8, are shown below: Image:Complete graph K1.svg| Image:Complete graph K2.svg| Image:Complete graph K3.svg| Image:Complete graph K4.svg| Image:Complete graph K5.svg| Image:Complete graph K6.svg| Image:Complete graph K7.svg| Image:Complete graph K8.svg|
| ||||||||
|
| |||||||||
 |
|
| |