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 aristas, y se denota . Es un grafo regular con todos sus vértices de grado . 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 (o el grafo bipartito completo ) y todo incluye a , entonces ningún grafo completo con es plano.
Ejemplos Los grafos completos de 1 a 12 nodos son los siguientes:
K1: 0 K2: 1 K3: 3 K4: 6 140px 140px 140px 140px K5: 10 K6: 15 K7: 21 K8: 28 140px 140px 140px 140px K9: 36 K10: 45 K11: 55 K12: 66 140px 140px 140px 140px
Véase también Grafo Teoría de grafos
Referencias
Categoría:Grafos regulares Categoría:Familias paramétricas de grafos KJPIH0UH9YBHBBYUIPIOIJUHU