En teoría de grafos , el teorema de Wagner es una caracterización matemática de grafos planos prohibidos , llamada así en honor a Klaus Wagner , que establece que un grafo finito es plano si y sólo si sus menores no incluyen ni K 5 (el gráfico completo en cinco vértices ) ni K 3, 3 (el gráfico de utilidad , un gráfico bipartito completo en seis vértices). Este fue uno de los primeros resultados en la teoría de grafos menores y puede verse como un precursor del teorema de Robertson-Seymour .
Una incrustación plana de un gráfico dado es un dibujo del gráfico en el plano euclidiano , con puntos para sus vértices y curvas para sus aristas , de tal manera que las únicas intersecciones entre pares de aristas están en un punto final común de las dos aristas. . Un gráfico menor de un gráfico dado es otro gráfico formado eliminando vértices, eliminando aristas y contrayendo aristas. Cuando se contrae una arista, sus dos puntos finales se fusionan para formar un solo vértice. En algunas versiones de la teoría de grafos menores, el gráfico resultante de una contracción se simplifica eliminando los bucles propios y las adyacencias múltiples, mientras que en otras versiones se permiten los multigrafos , pero esta variación no supone ninguna diferencia para el teorema de Wagner. El teorema de Wagner establece que cada gráfico tiene una incrustación plana o una menor de uno de dos tipos, el gráfico completo K 5 o el gráfico bipartito completo K 3,3 . (También es posible que un solo gráfico tenga ambos tipos de menores).
Si un gráfico dado es plano, también lo son todos sus menores: la eliminación de vértices y aristas obviamente preserva la planaridad, y la contracción de las aristas también se puede realizar de 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 incidieron en el otro punto final a lo largo del camino del borde contraído. Un gráfico no plano mínimo menor es un gráfico que no es plano, pero en el que todos los menores propios (menores formados por al menos una deleción o contracción) son planos. Otra forma de enunciar el teorema de Wagner es que sólo hay dos gráficos no planos de mínimos menores, K 5 y K 3,3 .
Otro resultado también conocido a veces como teorema de Wagner establece que un gráfico de cuatro conexos es plano si y sólo si no tiene K 5 menor. Es decir, al asumir un mayor nivel de conectividad, el gráfico K 3,3 puede hacerse innecesario en la caracterización, dejando solo un menor prohibido, K 5 . En consecuencia, la conjetura de Kelmans-Seymour establece que un grafo de 5 conexos es plano si y sólo si no tiene K 5 como topológico menor .
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 sólo si no contiene como subgrafo una subdivisión de uno de los mismos dos grafos prohibidos. K 5 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 menor del mismo tipo contrayendo todos los bordes menos uno en cada camino formado por el proceso de subdivisión, pero convirtiendo una menor en una subdivisión del mismo tipo. No siempre es posible. Sin embargo, en el caso de las dos gráficas K 5 y K 3,3 , es sencillo demostrar que una gráfica que tiene al menos una de estas dos gráficas como menor también tiene al menos una de ellas como subdivisión, por lo que la dos teoremas son equivalentes. [3]
Una consecuencia de la versión más fuerte del teorema de Wagner para gráficas de cuatro conexos es caracterizar las gráficas que no tienen un K 5 menor. El teorema se puede reformular para afirmar que cada gráfico de este tipo es plano o se puede descomponer en partes más simples. Usando esta idea, los gráficos K 5 sin menores pueden caracterizarse como los gráficos que se pueden formar como combinaciones de gráficos planos y el gráfico de Wagner de ocho vértices , pegados entre sí mediante operaciones de suma de camarillas . Por ejemplo, K 3,3 se puede formar de esta manera como una suma de camarilla de tres gráficos planos, cada uno de los cuales es una copia del gráfico tetraédrico K 4 .
El teorema de Wagner es un precursor importante de la teoría de grafos menores, que culminó con la demostración de dos resultados profundos y de gran alcance: el teorema de estructura de grafos (una generalización de la descomposición de suma de camarillas de Wagner de grafos libres de K 5 menores) [ 4] y el teorema de Robertson-Seymour (una generalización de la caracterización menor prohibida de grafos planos, afirmando que cada familia de grafos cerrada bajo la operación de tomar menores tiene una caracterización por un número finito de menores prohibidos). [5] Los análogos del teorema de Wagner también pueden extenderse a la teoría de las matroides : en particular, los mismos dos gráficos K 5 y K 3,3 (junto con otras tres configuraciones prohibidas) aparecen en una caracterización de las matroides gráficas como matroid prohibida. menores de edad . [6]