Grafo completo

De Wikipedia, la enciclopedia libre

En en el campo de la teoría de grafos, un grafo completo es aquél donde todas sus aristas conectan cada par de vértices. El grafo completo de n vértices tiene n vértices y $n (n - 1) / 2$ aristas, y se nota $K n$ . Es un grafo regular con todos sus vértices de grado $n - 1$ . Ningún grafo completo tiene lazos y está conectado totalmente, por ende, la única forma de hacer disconexo el grafo con una eliminación de vértices es aplicarla a todos.

El teorema de Kuratowski dice que un grafo planar no puede contener $K 5$ (ó 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 \ge 5$ es planar