Teorema de Kuratowski

En teoría de grafos, el teorema de Kuratowski, desarrollado por el matemático polaco Kazimierz Kuratowski, es una caracterización de los grafos planares.

Definición

Un grafo es planar si y sólo si no contiene un subgrafo que es subdivisión elemental de K₅ (el grafo completo de 5 vértices) o K_3,3 (el grafo bipartito completo de 6 vértices)

Kazimierz Kuratowski

Una subdivisión elemental de un grafo resulta de insertar vértices en las aristas (por ejemplo, cambiando •——• por •—•—•). Una formulación equivalente a este teorema es:

Un grafo es planar si y sólo si no contiene ningún subgrafo homeomorfo a K₅ o K_3,3.

Kazimierz Kuratowski

Ejemplo

¿El grafo K₆ completo puede ser plano?

Si se elimina un vértice de K₆ y todas las aristas que lo unen con el resto de vértices, se puede observar que el grafo K₆ contiene como subgrafo un K₅. Por el Teorema de Kuratowski se puede afirmar que el grafo K₆ no es planar.