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 ${\displaystyle n(n-1)/2}$ aristas, y se denota ${\displaystyle K_{n}}$. Es un grafo regular con todos sus vértices de grado ${\displaystyle 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 ${\displaystyle K_{5}}$ (o el grafo bipartito completo ${\displaystyle K_{3,3}}$) y todo ${\displaystyle K_{n}}$ incluye a ${\displaystyle K_{n-1}}$, entonces ningún grafo completo ${\displaystyle K_{n}}$ con ${\displaystyle n\geq 5}$ es plano.