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

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
K₇, grafo completo de 7 vértices.
Vértices	n
Aristas	n (n-1)/2
Diámetro	1
Cintura	3, si n ≥ 3
Automorfismos	n! (S_n)
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 Integral
[editar datos en Wikidata]

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.