Grafo completo

Carta Común · N.º 495434

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…

Leer en Wikipedia · Imagen David Benbennick, Public domain