Teorema de Kuratowski

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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[editar]

K5
K3,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)


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 ó K3,3.


Ejemplo[editar]

K6

¿El grafo K6 completo puede ser plano?

Se puede observar que el grafo K6 contiene como subgrafo un K5. Por el Teorema de Kuratowski se puede afirmar que el grafo K6 no es planar.