Grafos Planos

Se dice que un grafo es plano si y solo si puede dibujarse en el plano de manera que ningún par de sus aristas se corte.

Si tenemos, por ejemplo, el siguiente grafo, ¿es plano?

Efectivamente, lo es, porque se puede dibujar sin cruces entre las líneas como podemos ver en la figura siguiente:


Lo que asegura el teorema de Kuratowski es que los grafos planos son aquellos que no contienen ni al grafo K5 ni al grafo K 3,3, que son los que aparecen en la figura siguiente.

Ejemplo Practico