Un grafo completo de n vértices tiene

aristas, y se denota

Es un grafo regular con todos sus vértices de grado

La única forma de hacer que un grafo completo se torne disconexo a través de la eliminación de vértices, sería eliminándolos todos.

El teorema de Kuratowski dice que un grafo plano no puede contener

(o el grafo bipartito completo

Los grafos completos de 1 a 12 nodos son los siguientes: