Duro plana gráfico problema

Question

La triangulación se llama un plano gráfico en el que cada cara es un triángulo. Demostrar que en cada triangulación existe edge $\left\{ u,v \right\}$ tal que $\deg(u)+\deg(v)\le 22$. Dar un ejemplo de plano gráfico sin vértice de grado igual a 1, que no tiene este tipo de borde.

Parece ser muy duro (y extraño límite: $22$), sin embargo en la escuela que no había muy difíciles las cosas. Teníamos cuatro de color teorema de Euler característica, el teorema de Kuratowski, en el corto de todos los clásicos. Pero este problema.. yo no sé ni cómo empezar, e incluso imaginar un ejemplo de gráfico que debo darle en la segunda parte de este problema.

Ni siquiera puedo imaginar un ejemplo de triangulación.. supongo que incluso ilimitado cara debe ser un triángulo. Sólo que no veo.

Answer 1

Sugerencia:

Llame vértices de grado $< 12$ bajo grado y otros vértices de alto grado. Queremos encontrar un borde adyacente a la baja de dos de grado de los vértices.

En primer lugar demostrar que un mínimo de nidos contraejemplo tiene su grado mínimo $\geq 4$. En segundo lugar, muestra que al menos el $\frac{3}{4}$ de los vértices son de bajo grado. Último, encontrar el número de aristas en el grafo.

Answer 2

Ejemplo de plano gráfico sin vértice de grado igual a 1, que no tiene este tipo de borde:

Gráfico 23 de vértices, en el que dos vértices que distinguir. Distinguidos dos vértices tienen grado de 21, el resto tienen un grado de 2 y cada vértice tiene los bordes tanto de distinguidos vértices.

Y, a continuación, cada borde en uno de los extremos tiene vértice con grado de 2, en la segunda final con el grado de 21. 21 + 2 > 22