PROFILPELAJAR.COM

Una suma de cliques de dos grafos planos y el grafo de Wagner, formando un grafo libre de K₅

En teoría de grafos, el teorema de Wagner es una caracterización de grafos prohibidos en grafos planos, llamado así por Klaus Wagner. El teorema establece que un grafo finito es plano si y solo si sus menores no incluyen a K₅ (el grafo completo con cinco vértices) ni a K_3,3 (el grafo del problema de los tres servicios, un grafo bipartito completo con seis vértices). Este fue uno de los primeros resultados en la teoría de menores y puede verse como un precursor del teorema de Robertson-Seymour.

Definiciones y enunciado

Un embebido plano de un grafo dado es un dibujo del grafo en el espacio bidimensional, con puntos para sus vértices y curvas para sus aristas, de tal forma que las únicas intersecciones entre pares de aristas son en un punto final común de las dos aristas. Un menor de un grafo dado es otro grafo formado al eliminar vértices, eliminar aristas y contraer aristas. Cuando se contrae una arista, sus dos extremos se fusionan para formar un solo vértice. En algunas versiones de la teoría de grafos menores, el grafo resultante de una contracción se simplifica al eliminar los bucles propios y las adyacencias múltiples, mientras que en otras versiones se permiten multigrafos, pero esta variación no implica ninguna diferencia con respecto al teorema de Wagner.

El teorema establece que todo grafo tiene una incrustación plana o un menor de uno de dos tipos, el grafo completo K₅ o el grafo bipartito completo K_3,3 (también es posible que un solo grafo tenga ambos tipos de menores).

Si un grafo dado es plano, también lo son todos sus menores: la eliminación de vértices y bordes obviamente preserva la planaridad, y la contracción de los bordes también se puede hacer de una manera que preserve la planaridad, dejando uno de los dos puntos finales del borde contraído en su lugar y enrutando todos los bordes que inciden en el otro extremo en la ruta del borde contraído.

Un grafo no plano menor-mínimo es un grafo que no es plano, pero en el que todos los menores propios (menores formados por al menos una eliminación o contracción) son planos. Otra forma de enunciar el teorema de Wagner es que solo hay dos grafos no planos menores-mínimos, K₅ y K_3,3.

Otro resultado también conocido a veces como teorema de Wagner establece que un grafo 4-vértices-conectadp es plano si y solo si no tiene K₅ como menor. Es decir, al asumir un mayor nivel de conectividad, se puede hacer innecesario el grafo K_3,3 en la caracterización, quedando solo un único menor prohibido, K₅. Correspondientemente, la conjetura de Kelmans-Seymour establece que un grafo 5-conectado es plano si y solo si no tiene K₅ como menor.

Historia y relación con el teorema de Kuratowski

Wagner publicó ambos teoremas en 1937,^[1] posteriormente a la publicación en 1930 del teorema de Kuratowski,^[2] según el cual un grafo es plano si y solo si no contiene como subgrafo una subdivisión de uno de los mismos dos grafos prohibidos K₅ y K_3,3. En cierto sentido, el teorema de Kuratowski es más fuerte que el teorema de Wagner: una subdivisión se puede convertir en una subdivisión menor del mismo tipo contrayendo todos menos uno de los bordes en cada camino formado por el proceso de subdivisión, pero convirtiendo una subdivisión menor en una subdivisión del mismo tipo no siempre es posible. Sin embargo, en el caso de los dos grafos K₅ y K_3,3, es sencillo demostrar que un grafo que tiene al menos uno de estos dos grafos como menor también tiene al menos uno de ellos como una subdivisión, por lo que los dos teoremas son equivalentes.^[3]

Implicaciones

Una consecuencia de la versión más fuerte del teorema de Wagner para grafos cuatriconexos es caracterizar los grafos que no tienen a K₅ como menor. El teorema se puede reformular diciendo que cada grafo de este tipo es plano o se puede descomponer en partes más simples. Usando esta idea, los grafos libres del menor K₅ se pueden caracterizar como aquellos que se pueden formar como combinaciones de grafos planos y el grafo de Wagner de ocho vértices, unidos por operaciones de suma de cliques. Por ejemplo, K_3,3 se puede formar de esta manera como una suma de tres grafos planos, cada uno de los cuales es una copia del grafo tetraédrico K₄.

El teorema de Wagner es un importante precursor de la teoría de grafos menores, que culminó en la demostración de dos resultados profundos y de largo alcance: el teorema de la estructura del grafo (una generalización de la descomposición de suma de cliques de Wagner de grafos libres del menor K₅)^[4] y el teorema de Robertson–Seymour (una generalización de la caracterización de menores prohibidos de grafos planos, afirmando que toda familia de grafos cerrada bajo la operación de toma de menores tiene una caracterización por un número finito de menores prohibidos).^[5] Los análogos del teorema de Wagner también se pueden extender a la teoría de los matroides: en particular, los mismos dos grafos K₅ y K_3,3 (junto con otras tres configuraciones prohibidas) aparecen en una caracterización de los matroides gráficos por menores matroides prohibidos.^[6]