El teorema de Wagner es una caracterización de gráficos planos estrechamente relacionado con el teorema de Pontryagin-Kuratovsky .
El nombre de Klaus Wagner . El teorema establece que un grafo finito es plano si y solo si sus menores no incluyen ni K 5 ( un grafo completo con cinco vértices ) ni K 3,3 ( un grafo comunal , un grafo bipartito completo con tres vértices en cada parte). El teorema fue uno de los primeros trabajos 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 una visualización de un gráfico en el plano euclidiano , representado por puntos como vértices y curvas como bordes, mientras que los bordes solo pueden tener puntos comunes en los extremos de los bordes (en los vértices del gráfico). El menor de un grafo dado es otro grafo obtenido quitando vértices, quitando y contrayendo aristas. Cuando un borde se contrae, sus extremos se fusionan en un vértice. En algunas versiones de la teoría de grafos menores, el gráfico obtenido después de la contracción de los bordes se simplifica eliminando bucles y múltiples bordes, mientras que en otras versiones se permiten multigrafos , pero estas variaciones no son esenciales para el teorema de Wagner. El teorema de Wagner establece que cualquier gráfico tiene una incrustación plana o contiene un menor de uno de dos tipos: un gráfico completo K 5 o un gráfico bipartito completo K 3,3 (un gráfico puede tener ambos tipos de menores).
Si el gráfico dado es plano, también lo son todos sus menores: eliminar un vértice o una arista obviamente no viola la planaridad, y la contracción de una arista también se puede hacer conservando la planaridad, si uno de los vértices de la arista que se contrae es dejado en su lugar, y todos los bordes incidentes al segundo vértice están a lo largo del borde contraído. Un gráfico no plano menor-mínimo es un gráfico no plano, pero todos sus menores propios (menores obtenidos al eliminar o contraer al menos un borde) son planos. Otra formulación del teorema de Wagner es que solo hay dos grafos no planos menores-mínimos, estos son K 5 y K 3,3 .
Otro resultado, a veces también llamado teorema de Wagner, establece que un grafo con 4 vértices conexos es plano si y solo si no contiene K 5 como menor. Es decir, bajo el supuesto de un mayor nivel de conectividad, el grafo K 3,3 resulta ser irrelevante para la descripción, por lo que solo queda un menor prohibido, K 5 . En consecuencia, la conjetura de Kelmans-Seymour establece que un grafo conectado por el vértice 5 es plano si y solo si no contiene K 5 como un menor topológico .
Wagner publicó ambos teoremas en 1937 [1] , ya después de la publicación de Kuratowski en 1930 [2] del teorema , según el cual un grafo es plano si y solo si no contiene como subgrafo una subdivisión de uno de los mismos grafos prohibidos K 5 y K 3 ,3 . 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 ruta de reducción de escala, pero la conversión de una subdivisión menor a una subdivisión del mismo tipo no siempre es posible. Sin embargo, en el caso de dos grafos K 5 y K 3,3 , se puede demostrar directamente que a partir de estos grafos por subdivisión se puede obtener un grafo que contenga al menos uno de estos grafos como menor, por lo que los dos teoremas son equivalentes [ 3] .
Una de las consecuencias de la versión del teorema de Wagner para grafos cuatriconexos es la descripción de grafos que no contienen K 5 como menor. El teorema se puede reformular diciendo que cualquier gráfico de este tipo es plano o se puede descomponer en partes más simples. Usando esta idea, las gráficas que no contienen K 5 como menor pueden describirse como gráficas formadas por combinaciones de una gráfica plana y una gráfica de Wagner de seis vértices unidas por sumas de clique . Por ejemplo, K 3,3 puede generarse de esta manera mediante sumas de clique 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 importante precursor de la teoría de los grafos menores, que alcanzó su apogeo al probar dos resultados profundos con amplias consecuencias: el teorema estructural del grafo (una generalización de la descomposición de Wagner en sumas grupales de grafos que no contienen K 5 como menor) [ 4] y el teorema de Robertson-Seymour (una generalización de la descripción de grafos usando menores prohibidos, afirmando que cualquier familia de grafos cerrada por la operación de tomar un menor es descrita por un número finito de menores prohibidos) [5] . La analogía del teorema de Wagner se puede extender a la teoría matroide . En particular, los mismos K 5 y K 3,3 (junto con otros tres) aparecen en la descripción de matroides gráficos como matroides menores prohibidos [6] .