Si un gráfico no tiene ninguna subdivisión K4 o K2,3, entonces es outerplanar

Question

¿Es éste un argumento válido para demostrar la afirmación? He puesto en negrita la parte que más dudo:

Si un gráfico no tiene $K_{4}$ o $K_{2,3}$ subdivisión entonces es outerplanar

Supongamos que G no tiene $K_{4}$ o $K_{2,3}$ . Añadir un vértice $v$ a la cara exterior de $G$ (fuera de $G$ ) y conectarlo a cada vértice de $G$ . Llama a este gráfico $G^{\prime}$ . Supongamos que $G^{\prime}$ no es planar y por el teorema de Kuratowski contiene un $K_{5}$ o $K_{3,3}$ subdivisión. Por lo tanto, $G$ debe contener un $K_{4}$ o $K_{2,3}$ subdivisión, ya que cada $K_{5}$ La subdivisión contiene un $K_{4}$ y cada $K_{3,3}$ contiene un $K_{2,3}$ subdivisión . Sin embargo, por la suposición $G$ no tiene un $K_{4}$ o $K_{2,3}$ subdivisión, por lo que tenemos una contradicción. Por lo tanto, $G^{\prime}$ debe ser planar. Como $G^{\prime}$ es plana y $v$ es exterior a todos los $G$ y adyacente a todos los vértices de $G$ , $G$ debe ser exterior al plano.

Answer 1

En primer lugar, se empieza por añadir vértices $v$ a la "cara exterior de $G$ ", y posteriormente utilizando el hecho de que $v$ es "exterior a todo $G$ ".

Esto no está bien, ya que en este momento, no sabemos que $G$ es planar, y no tienen una incrustación plana fija de $G$ . Incluso si se invoca el teorema de Kuratowski para decir que $G$ es planar y escogemos una incrustación plana, ¡podría ser la incrustación incorrecta para que la usemos después! Demostraremos que $G'$ tiene una incrustación plana más adelante, pero esa incrustación plana podría no ser compatible con la incrustación plana que elegimos para $G$ .

(Tenga en cuenta también que aunque $G$ es exteriormente plana, no todas las incrustaciones planas de ella son incrustaciones exteriormente planas. Algunas incrustaciones pueden tener todos los vértices a lo largo de una cara que no es la cara exterior; otras pueden no tener ninguna cara de este tipo).

Así que en el primer paso, todo lo que podemos hacer es decir "construir $G'$ añadiendo un nuevo vértice $v$ adyacente a todos los vértices de $G$ ". Esto estará bien.

---

Para justificar el paso en negrita, considere una subdivisión de, digamos, $K_5$ sur $G'$ .

• Si no contiene el nuevo vértice $v$ Estamos bien; es una subdivisión de $K_5$ sur $G$ y esto contiene una subdivisión de $K_4$ .
• Si contiene $v$ a lo largo de un borde subdividido, entonces olvídate de todo ese borde subdividido. Obtenemos una subdivisión de $K_5 - e$ sur $G$ que todavía contiene una subdivisión de $K_4$ .
• Si contiene $v$ como uno de los $K_5$ vértices, entonces olvídate de ese vértice y de todas las aristas subdivididas fuera de él. Obtenemos una subdivisión de $K_4$ sur $G$ .

El mismo argumento sirve para $K_{3,3}$ .

---

Hay que tener más cuidado con el último paso: sólo porque $G'$ es planar, podemos concluir que $G$ ¿es outerplanar?

Tomemos un dibujo plano de $G'$ . Eliminación de $v$ y todas sus aristas da un dibujo plano de $G$ . Sea $S$ sea el subconjunto del plano donde $v$ y todos sus bordes estaban incrustados. A continuación,

1. $S$ es un subconjunto conexo del plano que no interseca ningún vértice o arista de $G$ , por lo que está contenida por completo en alguna cara de $G$ .
2. Desde $S$ contiene puntos arbitrariamente cercanos a los vértices de $G$ están incrustados, esa cara de $G$ contiene todos los vértices.

Así que tenemos una incrustación de $G$ donde una de las caras contiene todos los vértices. Si ya es exterior, bien. Si no, podemos invertir el plano sobre un punto contenido en esta cara, y obtener una nueva incrustación de $G$ donde es la cara exterior.