Grafo completo

Grafo completo
K7, grafo completo de 7 vértices.
Vértices	n
Aristas	n (n-1)/2
Diámetro	1
Cintura (girth)	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

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 $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

Ejemplos

Los grafos completos de 1 a 12 vértices son los siguientes:

• 

  $K_1: 0$

• 

  $K_2: 1$

• 

  $K_3: 3$

• 

  $K_4: 6$

• 

  $K_5: 10$

• 

  $K_6: 15$

• 

  $K_7: 21$

• 

  $K_8: 28$

• 

  $K_9: 36$

• 

  $K_{10}: 45$

• 

  $K_{11}: 55$

• 

  $K_{12}: 66$