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

Grafo completo
Complete graph K7.svg
K7, grafo completo de 7 vértices.
Vértices n
Aristas n (n-1)/2
Diámetro 1
Cintura 3, si n ≥ 3
Automorfismos n! (Sn)
Número cromático n
Índice cromático n, si n es impar
n-1, si n es par
Propiedades (n-1)-regular
Simétrico
Vértice transitivo
Arista transitivo
Distancia unidad
Fuertemente regular
Integral

Un grafo completo de n vértices tiene aristas, y se nota . 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 (ó el grafo bipartito completo ) y todo incluye a , entonces ningún grafo completo con es plano.

EjemplosEditar

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

K1: 0 K2: 1 K3: 3 K4: 6
       
K5: 10 K6: 15 K7: 21 K8: 28
       
K9: 36 K10: 45 K11: 55 K12: 66
       

Véase tambiénEditar

ReferenciasEditar