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.

Grafo completo
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 $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.

Ejemplos

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én

• Grafo
• Teoría de grafos

Referencias

• Datos: Q45715
• Multimedia: Complete graphs / Q45715

KJPIH0UH9YBHBBYUIPIOIJUHU