Grafo completo

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

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