Complete graph

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 planar graph cannot contain <math>K_5<math> (or the complete bipartite graph <math>K_{3,3}<math>) as a minor.

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