Teorema de wagner

En teoría de grafos, el teorema de Wagner es una caracterización matemática de grafos planos prohibidos, que lleva el nombre de Klaus Wagner, y que establece que un grafo finito es plano si y sólo si sus menores no incluyen ninguno de los dos. K₅ (el gráfico completo en cinco vértices) ni K_3,3 (el gráfico de utilidad, un gráfico completo gráfico bipartito 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.

Definiciones y declaraciones

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 los dos bordes. 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 todo grafo tiene una incrustación plana o una menor de uno de dos tipos, el grafo completo K₅ o el grafo bipartito completo < i>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 Coloque y enrute todos los bordes que incidieron en el otro punto final a lo largo del camino del borde contraído. Un gráfico no plano menor-mínimo 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áficas no planas mínimas menores, K₅ y K< sub>3,3.

Otro resultado también conocido como teorema de Wagner establece que un grafo de cuatro conexos es plano si y sólo si no tiene ningún K₅ 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 único menor prohibido, K. ₅. En consecuencia, la conjetura de Kelmans-Seymour establece que un grafo de 5 conexos es plano si y sólo si no tiene K₅ como menor topológico.

Historia y relación con el teorema de Kuratowski

Wagner publicó ambos teoremas en 1937, después de la publicación en 1930 del teorema de Kuratowski, 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 prohibidos. gráficas 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 menor del mismo tipo contrayendo todos los bordes menos uno en cada camino formado por el proceso de subdivisión, pero convirtiendo un minor en una subdivisión del mismo tipo no siempre es posible. Sin embargo, en el caso de las dos gráficas 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 subdivisión, por lo que los dos teoremas son equivalentes.

Implicaciones

Una consecuencia de la versión más fuerte del teorema de Wagner para grafos de cuatro conexos es caracterizar los grafos que no tienen un K₅ 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, las gráficas libres menores K₅ se pueden caracterizar como las gráficas que se pueden formar como combinaciones de gráficas planas y la gráfica de Wagner de ocho vértices, pegadas. juntos mediante operaciones de suma camarilla. 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₄.

El teorema de Wagner es un precursor importante de la teoría de los grafos menores, que culminó con la demostración de dos resultados profundos y de gran alcance: el teorema de la estructura de los grafos (una generalización del teorema de suma camarilla de Wagner). descomposición de K₅-gráficos libres menores) y el teorema de Robertson-Seymour (una generalización de la caracterización menor prohibida de los gráficos planos, que establece que toda familia de gráficos se cierra bajo el operación de acogida de menores se caracteriza por un número finito de menores prohibidos). Los análogos del teorema de Wagner también se pueden extender a la teoría de las matroides: en particular, las mismas dos gráficas K₅ y K _3,3 (junto con otras tres configuraciones prohibidas) aparecen en una caracterización de las matroides gráficas por matroides menores prohibidas.