Grafo completo

Plantilla:Ficha de grafo En teoría de grafos, un grafo completo es un grafo simple donde cada par de vértices está conectado por una arista.

Un grafo completo de n vértices tiene $n (n - 1) / 2$ aristas, y se denota $K_{n}$ . Es un grafo regular con todos sus vértices de grado $n - 1$ . 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 $K_{5}$ (o el grafo bipartito completo $K_{3, 3}$ ) y todo $K_{n}$ incluye a $K_{n - 1}$ , entonces ningún grafo completo $K_{n}$ con $n \geq 5$ es plano.