Grafo completo

Grafo completo
	Archivo: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
	Página no enlazada a Wikidata Si no existe en otras Wikipedias: [crea nuevo ítem]; Si existe en otras Wikipedias: [busca ítem para enlazar]; y añade el enlace en español: 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.

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:

K₁: 0	K₂: 1	K₃: 3	K₄: 6
Archivo:Complete graph K1.svg	Archivo:Complete graph K2.svg	Archivo:Complete graph K3.svg	Archivo:3-simplex graph.svg
K₅: 10	K₆: 15	K₇: 21	K₈: 28
Archivo:4-simplex graph.svg	Archivo:5-simplex graph.svg	Archivo:6-simplex graph.svg	Archivo:7-simplex graph.svg
K₉: 36	K₁₀: 45	K₁₁: 55	K₁₂: 66
Archivo:8-simplex graph.svg	Archivo:9-simplex graph.svg	Archivo:10-simplex graph.svg	Archivo:11-simplex graph.svg

Véase también

Referencias

KJPIH0UH9YBHBBYUIPIOIJUHU