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 aristas, y se nota . Es un grafo regular con todos sus vértices de grado . 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 (ó el grafo bipartito completo ) y todo incluye a , entonces ningún grafo completo con es planar

Los grafos completos de vértices, para entre 1 y 8 son estos:

Este artículo está licenciado sobre GNU Free Documentation License. Es una adaptación de Wikipedia "Grafo completo".