El dos de febrero de 1896, nacía en Varsovia el matemático y lógico polaco Kazimierz Kuratowski.
Se hizo profesor de matemáticas en 1927 en el politécnico de Leópolis (entonces parte de Polonia), desde 1934 pasó a enseñar en la Universidad de Varsovia. En 1945 se hizo miembro de la Academia Polaca de Ciencias. De 1948 a 1967 fue director del Instituto de Matemáticas de la Academia Polaca de Ciencias, así como presidente de la Unión Matemática Internacional.
Su investigación se basó en estructuras abstractas topológicas y métricas. En esta entrada nos centraremos en la teoría de grafos, en particular, en la caracterización de los grafos planares.
Para empezar, imaginemos que en un papel dibujamos tres casas situadas en una fila horizontal, cada una separada de su vecina y, paralelamente a ellas, las tomas de: agua, electricidad y gas. A continuación, queremos unir cada una de las casas con las tres tomas, sin que el trayecto corte ningún cable ni tubería.
Para esta unión, lo más eficiente es representar cada casa y toma con puntos (vértices), así como cada línea de conexión (aristas), de esta manera obtenemos el siguiente grafo:
Ahora bien, si denotamos por u1, u2 y u3 los vértices superiores, por v1, v2 y v3 los inferiores y asignamos uivj a la arista que une el vértice ui con el vértice vj, obtenemos el grafo conocido como K3,3:
K3,3 = {uivj / i, j = 1, 2, 3}
Hay que tener en cuenta que para que un grafo sea plano, dos aristas sólo se pueden cortar en un vértice, es decir, debemos poder realizar el dibujo sin levantar el bolígrafo del papel y sin cortar ninguna arista.
Antes de decir cuál es la solución, vamos a definir otro grafo, K5:
K5 = {uiuj / i = 1, 2, 3, 4, 5}
Es decir, K5 es un grafo que consta de 5 vértices y que tiene como aristas todas las líneas que conectan cada vértice con el resto. También se le conoce como grafo completo de 5 vértices.
Ahora ya estamos preparados para la solución:
Teorema de Kuratowski: Un grafo es planar si y sólo si no contiene como subgrafo a K5 ni K3,3
Por tanto, ni K5 ni K3,3 son grafos planos.
