Complete graph

From Wikipedia, the free encyclopedia

Image:K100 1280x1280.png 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 <math>n</math> vertices has <math>n</math> vertices and <math>n(n-1)/2</math> edges, and is denoted by <math>K_n</math>. It is a regular graph of degree <math>n-1</math>. 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 <math>K_3</math> relates to a triangle, <math>K_4</math> a tetrahedron, <math>K_5</math> a pentachoron, etc.

Kuratowski's theorem says that a planar graph cannot contain <math>K_5</math> (or the complete bipartite graph <math>K_{3,3}</math>) as a minor. Since <math>K_n</math> includes <math>K_{n-1}</math>, no complete graph <math>K_n</math> with <math>n</math> greater than or equal to 5 is planar.

Complete graphs on <math>n</math> vertices, for <math>n</math> between 1 and 8, are shown below: