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