En teoría de grafos , el teorema de Wagner es una caracterización matemática prohibida de grafos planares , llamada así por Klaus Wagner , que establece que un grafo finito es planar si y solo si sus menores no incluyen ni K 5 (el grafo completo en cinco vértices ) ni K 3,3 (el grafo de utilidad , un grafo bipartito completo en seis vértices). Este fue uno de los primeros resultados en la teoría de los menores de grafos y puede verse como un precursor del teorema de Robertson-Seymour .
Una incrustación plana de un grafo dado es un dibujo del grafo 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 menor de un grafo dado es otro grafo formado al eliminar vértices, eliminar aristas y contraer aristas. Cuando una arista se contrae, sus dos puntos finales se fusionan para formar un único vértice. En algunas versiones de la teoría de menores de grafos, el grafo resultante de una contracción se simplifica eliminando bucles propios y adyacencias múltiples, mientras que en otras versiones se permiten multigrafos , pero esta variación no hace ninguna diferencia para el teorema de Wagner. El teorema de Wagner establece que cada grafo tiene una incrustación plana o un menor de uno de dos tipos, el grafo completo K 5 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 aristas obviamente preserva la planaridad, y la contracción de aristas también se puede hacer de una manera que preserve la planaridad, dejando uno de los dos puntos finales de la arista contraída en su lugar y enrutando todas las aristas que eran incidentes al otro punto final a lo largo del camino de la arista contraída. 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 5 y K 3,3 .
Otro resultado, también conocido a veces como teorema de Wagner, establece que un grafo cuatriconexo es planar si y solo si no tiene ningún menor K 5 . Es decir, al suponer un nivel de conectividad más alto, el grafo K 3,3 puede hacerse innecesario en la caracterización, dejando solo un único menor prohibido, K 5 . En consecuencia, la conjetura de Kelmans-Seymour establece que un grafo 5-conexo es planar si y solo si no tiene K 5 como menor topológico .
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 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 un menor del mismo tipo contrayendo todas las aristas menos una en cada camino formado por el proceso de subdivisión, pero convertir un menor en una subdivisión del mismo tipo no siempre es posible. Sin embargo, en el caso de los dos grafos K 5 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 subdivisión, por lo que los dos teoremas son equivalentes. [3]
Una consecuencia de la versión más fuerte del teorema de Wagner para grafos con cuatro conexiones es caracterizar los grafos que no tienen un menor K 5 . El teorema puede reformularse para afirmar que cada uno de esos grafos es plano o puede descomponerse en piezas más simples. Usando esta idea, los grafos sin menores K 5 pueden caracterizarse como los grafos que pueden formarse como combinaciones de grafos planos y el grafo de Wagner de ocho vértices , pegados entre sí mediante operaciones de suma de camarillas . Por ejemplo, K 3,3 puede formarse de esta manera como una suma de camarillas de tres grafos planos, cada uno de los cuales es una copia del grafo tetraédrico K 4 .
El teorema de Wagner es un precursor importante de la teoría de los menores de grafos, que culminó en las demostraciones de dos resultados profundos y de largo alcance: el teorema de la estructura del grafo (una generalización de la descomposición en suma de camarillas de Wagner de grafos libres de menores K 5 ) [4] y el teorema de Robertson-Seymour (una generalización de la caracterización de menores prohibidos de grafos planares, que establece 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 se pueden extender a la teoría de matroides : en particular, los mismos dos grafos K 5 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]