¿Alguien sabe de una elegante prueba el hecho de que cada outerplanar gráfico tiene un vértice de grado en la mayoría de los 2 (y, por tanto, es de 2 degenerada, ya que cada subgrafo es también outerplanar).
Tengo una prueba por inducción (sobre el número de vértices) en mente, pero es larga y un poco engorroso (se divide en un par de casos). Puede alguien me apunte a un más elegante de la prueba?
Tal vez uno lo puede hacer utilizando el grafo dual - si el grafo dual es círculo libre, entonces hemos terminado, pero no pude encontrar un argumento fácil para que cualquiera.
Gracias de antemano por cualquier ayuda.
Respuestas
¿Demasiados anuncios?
Croquis de la prueba: por contradicción. Se asume que un outerplanar gráfico de $G$ existe en el que cada vértice tiene grado $\ge3$. $G$ no es un árbol, desde un árbol trivialmente tiene un vértice con grado de $\le2$. Por lo tanto, incluye al menos una región del interior, y que no tiene "ramas desnudas", (como iba a terminar con el grado 1.) Considerar el ciclo de atravesar el infinito de la cara de la gráfica. Si no es Hamiltoniano, entonces tiene al menos un subcycle sin vértices repetidos, conectado con el resto de la gráfica en sólo uno de sus vértices, es decir, "pellizcado" de el resto de la gráfica. Este subgrafo es Hamiltoniano y outerplanar, pero podemos demostrar que todos los Hamiltonianos outerplanar grafo tiene al menos dos vértices de grado exactamente dos, y al menos uno de estos tiene un total de grado 2 en $G$, una contradicción.
user8269
Puntos
46
