Cada plano gráfico es una unión de $3$ bosques

Question

Actualmente estoy trabajando en problemas relacionados con la planaridad en los gráficos, y Me encontré con un problema peculiar relativa a demostrar la relación entre grafos planares y los bosques.

Tomar un plano gráfico de $P$. Me imagino que me quiere inducir a $P$ a satisfacer Nash-Williams teorema. Fue una sugerencia que me considere la posibilidad de probar que un plano gráfico tiene en la mayoría de las $3n-6$ bordes, que por Nash-Williams implica que un plano gráfico se puede dividir en $\frac{3n-6}{n-1} = 3$ bosques. Sé que un plano gráfico satisface $v-e+f = 2$ donde $v$ es el número de vértices, $e$ es el número de aristas, y $f$ es el número de caras. Si puedo contradicen la afirmación de que $e > 3v-6$, que puede ser capaz de concluir esta prueba.

Vemos que si suponemos que por el bien de la contradicción $e > 3v-6$, vemos que $$-e < -3v + 6 \implies v-e < -2v + 6 \implies v-e+f < -2v+f+6,$$ que por planaridad implica que $-2v +f + 6 = 3.$ sin Embargo, estoy teniendo problemas en dónde pasar aquí. Hay una contradicción se encuentra en esta condición?

Answer 1

Su prueba puede estar en el camino equivocado, dado que sólo se puede utilizar la fórmula de Euler si el gráfico está conectado, y no puedo pensar en cómo hacer que funcione. Yo proporcionan una prueba por debajo de la cual utiliza las triangulaciones, que están conectados y la fórmula de Euler se aplicará.

Esta desigualdad es bien conocida. Para $n=1$ $n=2$ es obvio. En primer lugar observamos que cada plano gráfico con $v\ge 3$ vértices es un subgrafo de un avión de la triangulación con el mismo conjunto de vértices (un plano gráfico donde todas las caras tienen un grado $3$). Para ver esto, para cada cara con grado mayor que $3$, se puede elegir un vértice $u$ sobre sus límites y agregar nuevas aristas de $u$ a todos los vértices no adyacentes en el límite de la cara; el gráfico resultante es una triangulación.

Deje $e^\prime$ el número de aristas de la triangulación. Aquí, hay $3$ bordes por la cara, por lo $3f=2e^\prime$ (cada borde es adyacente a dos caras). Luego, por la fórmula de Euler, $$3e^\prime=3(v+f-2)=3v+2e^\prime-6.$$ Desde su grafo es un subgrafo de la triangulación, $e\le e^\prime$; por lo tanto, después de la reorganización, $$e\le 3v-6.$$