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 $K\_n$. 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 planar graph cannot contain $K\_5$ (or the complete bipartite graph $K\_\{3,3\}$) as a minor. Since $K\_n$ includes $K\_\{n-1\}$, no complete graph $K\_n$ with $n$ greater than or equal to 5 is planar.

Complete graphs on $n$ vertices, for $n$ between 1 and 8, are shown below:

Image:Complete graph K1.svg|$K\_1$ Image:Complete graph K2.svg|$K\_2$ Image:Complete graph K3.svg|$K\_3$ Image:Complete graph K4.svg|$K\_4$ Image:Complete graph K5.svg|$K\_5$ Image:Complete graph K6.svg|$K\_6$ Image:Complete graph K7.svg|$K\_7$ Image:Complete graph K8.svg|$K\_8$

Graphs

Úplný graf | Vollständiger Graph | Graphe complet | 완전 그래프 | Grafo completo | Pilnasis grafas | Graf pełny | Grafo completo | Polni graf | กราฟบริบูรณ์ | Đồ thị đầy đủ | 完全圖