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

K₅

K_3,3

Un grafo es planar si y sólo si no contiene un subgrafo que es subdivisión elemental de K5 (el grafo completo de 5 vértices) o K3,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 K5 o K3,3. Kazimierz Kuratowski

Ejemplo

K₆

¿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.

• Datos: Q837902