Teorema de Kuratowski

En teoría de grafos , el teorema de Kuratowski es una caracterización matemática de grafos planares prohibidos , que recibe su nombre de Kazimierz Kuratowski . Establece que un grafo finito es planar si y solo si no contiene un subgrafo que sea una subdivisión de${\displaystyle K_{5}}$(el grafo completo de cinco vértices ) ni de${\displaystyle K_{3,3}}$(un grafo bipartito completo de seis vértices, tres de los cuales se conectan con cada uno de los otros tres, también conocido como grafo de utilidad ).

Un grafo planar es aquel cuyos vértices pueden representarse mediante puntos en el plano euclidiano y cuyas aristas pueden representarse mediante curvas simples en el mismo plano que conectan los puntos que representan sus extremos, de manera que no haya dos curvas que se intersequen excepto en un extremo común. Los grafos planares suelen representarse con segmentos de línea recta que representan sus aristas, pero según el teorema de Fáry, permitir aristas curvas o requerir aristas rectas no afecta a su caracterización desde el punto de vista de la teoría de grafos.

Una subdivisión de un grafo es un grafo formado al subdividir sus aristas en caminos de una o más aristas. El teorema de Kuratowski establece que un grafo finito${\displaystyle G}$es planar si no es posible subdividir los bordes de${\displaystyle K_{5}}$o${\displaystyle K_{3,3}}$y luego posiblemente agregar aristas y vértices adicionales, para formar un grafo isomorfo a${\displaystyle G}$. De forma equivalente, un grafo finito es planar si y solo si no contiene un subgrafo que sea homeomorfo a${\displaystyle K_{5}}$o${\displaystyle K_{3,3}}$.

Si${\displaystyle G}$es un grafo que contiene un subgrafo${\displaystyle H}$que es una subdivisión de${\displaystyle K_{5}}$o${\displaystyle K_{3,3}}$, entonces${\displaystyle H}$se conoce como un subgrafo de Kuratowski de${\displaystyle G}$. ^{[ 1 ]} Con esta notación, el teorema de Kuratowski se puede expresar sucintamente: un grafo es planar si y solo si no tiene un subgrafo de Kuratowski.

Los dos gráficos${\displaystyle K_{5}}$y${\displaystyle K_{3,3}}$son no planares, como se puede demostrar mediante un análisis de caso o un argumento que involucre la fórmula de Euler . Además, subdividir un grafo no puede convertir un grafo no planar en un grafo planar: si una subdivisión de un grafo${\displaystyle G}$tiene un dibujo plano, las trayectorias de la subdivisión forman curvas que pueden usarse para representar los bordes de${\displaystyle G}$Por lo tanto, un grafo que contiene un subgrafo de Kuratowski no puede ser planar. La parte más difícil de demostrar el teorema de Kuratowski consiste en mostrar que, si un grafo no es planar, debe contener un subgrafo de Kuratowski.

Un subgrafo de Kuratowski de un grafo no planar se puede encontrar en tiempo lineal , medido por el tamaño del grafo de entrada. ^{[ 2 ]} Esto permite verificar la corrección de un algoritmo de prueba de planaridad para entradas no planas, ya que es sencillo comprobar si un subgrafo dado es o no un subgrafo de Kuratowski. ^{[ 3 ]} Por lo general, los grafos no planares contienen un gran número de subgrafos de Kuratowski. La extracción de estos subgrafos es necesaria, por ejemplo, en algoritmos de ramificación y corte para la minimización de cruces. Es posible extraer un gran número de subgrafos de Kuratowski en un tiempo que depende de su tamaño total. ^{[ 4 ]}

Kazimierz Kuratowski publicó su teorema en 1930. ^{[ 5 ]} El teorema fue demostrado independientemente por Orrin Frink y Paul Smith , también en 1930, ^{[ 6 ]} pero su demostración nunca fue publicada. El caso especial de grafos planares cúbicos (para los cuales el único subgrafo prohibido mínimo es${\displaystyle K_{3,3}}$) también fue demostrado independientemente por Karl Menger en 1930. ^{[ 7 ]} Desde entonces, se han descubierto varias demostraciones nuevas del teorema. ^{[ 8 ]}

En la Unión Soviética , el teorema de Kuratowski era conocido como el teorema de Pontryagin-Kuratowski o el teorema de Kuratowski-Pontryagin , ^{[ 9 ]} ya que, según se informa , Lev Pontryagin lo demostró de forma independiente alrededor de 1927. ^{[ 10 ]} Sin embargo, como Pontryagin nunca publicó su demostración, este uso no se ha extendido a otros lugares. ^{[ 11 ]}

Un resultado estrechamente relacionado, el teorema de Wagner , caracteriza los grafos planares mediante sus menores en términos de los mismos dos grafos prohibidos.${\displaystyle K_{5}}$y${\displaystyle K_{3,3}}$Todo subgrafo de Kuratowski es un caso especial de un menor del mismo tipo, y aunque lo contrario no es cierto, no es difícil encontrar un subgrafo de Kuratowski (de un tipo u otro) a partir de uno de estos dos menores prohibidos; por lo tanto, estos dos teoremas son equivalentes. ^{[ 12 ]}

Una extensión de este teorema es el teorema de Robertson-Seymour , que establece que toda clase de grafos cerrados bajo la operación de tomar menores (como lo son los grafos planares) puede caracterizarse de manera análoga mediante un conjunto finito de menores prohibidos.

• Conjetura de Kelmans-Seymour , que los grafos no planares 5-conectados contienen una subdivisión de${\displaystyle K_{5}}$