Una duda en la demostración del teorema de Kuratowski

Question

Al tratar de entender la demostración del teorema de Kuratowski (es decir, un gráfico es plano si y sólo si no contiene ninguna subdivisión de $K_5$ o $K_{3,3}$ ) de este libro (Página 299) En primer lugar, estoy tratando de entender la prueba del hecho de que un gráfico mínimo no planar donde cada vértice es de grado al menos $3$ es $3$ -conectado.

La prueba del libro está en las siguientes líneas. Comenzamos observando que $G$ es $2$ -conectado. A modo de contradicción, suponemos entonces que $G=G_1\cup G_2$ con $V(G_1)\cap V(G_2)=\{x,y\},|V(G_i)|\ge 3$ . Sea $P_i$ ser un $(x,y)$ camino en $G_i$ y $H_i=G_i+P_{3-i}$ . Entonces $H_i$ es planar y podemos incrustar $H_i$ en el plano para que la trayectoria $P_{3-i}$ está en el límite del dominio no limitado (esto se puede conseguir invirtiendo el plano con respecto a un círculo apropiado). (Y entonces la prueba continúa).

No entiendo la última afirmación "podemos incrustar $H_i$ en el plano para que la trayectoria $P_{3-i}$ está en la frontera del dominio no limitado". ¿Puede alguien explicar por qué es así? Hice una pregunta más general al respecto aquí pero la respuesta a eso no resuelve el problema aquí. ¿Qué significa "invertir el plano con respecto a un círculo apropiado"?

Answer 1

Los grafos planos, por definición, son grafos que pueden representarse (dibujarse) en el plano euclidiano utilizando puntos distintos para los vértices y caminos continuos mutuamente disjuntos entre esos puntos para las aristas que los unen. Si eliminamos la condición de "mutuamente disjuntos", cualquier grafo finito puede representarse de esta manera.

La definición sería equivalente si sustituyéramos el plano euclidiano por la esfera. La proyección estereográfica del Polo Norte sobre el plano tangente al Polo Sur establece el homeomorfismo necesario entre la esfera (menos un punto, el Polo Norte) y el plano euclidiano. Los puntos cercanos al Polo Norte se proyectan sobre puntos alejados del origen del plano euclidiano y alejados de la consiguiente representación euclidiana del gráfico.

Pero la esfera se puede girar con respecto al gráfico para que el Polo Norte se encuentre realmente dentro de uno de los bucles interiores. De hecho, para cualquier arista del gráfico existen rotaciones de la esfera que sitúan el Polo Norte en una región adyacente a esa arista.

La aplicación de la proyección estereográfica a la nueva situación garantiza que la arista dada aparezca en el exterior de la nueva representación euclidiana del gráfico.

Supongo que el autor entiende por "círculo" cualquier componente conexo acotado de la complemento de la representación gráfica. He llamado a esto "bucle interno", pero es lo mismo. Cuando el autor dice "dominio no limitado" se refiere al único componente conectado no limitado del complemento de la representación del gráfico.

Ahora $P_{3-i}$ en la prueba es un camino, no una arista. Pero su papel topológico en $H_i$ es lo mismo que si fuera una sola arista, porque $P_{3-i}\cap G_i=\{x,y\},$ es decir, ninguno de los puntos intermedios del camino tiene aristas (en $H_i$ ) aparte de las dos aristas que lo hacen parte del camino. Por lo tanto, cualquier círculo de $H_i$ que es adyacente a una sola arista de $P_{3-i}$ es adyacente a todas las aristas de $P_{3-i}$ y, en consecuencia, la construcción anterior que hace girar el Polo Norte junto a un borde de $P_{3-i}$ garantiza que todo bordes del camino $P_{3-i}$ están en el exterior de la nueva representación euclidiana.