Demostrar que un plano gráfico tiene cuatro colorear

Question

Hay un teorema que dice que cada plano gráfico puede ser coloreado con cinco colores. También puede ser coloreado con cuatro colores. ¿Cómo puedo demostrar que el plano gráfico con el grado máximo de $4$, tiene un cuatro para colorear?

Alguien me puede ayudar demostrar esto?

Answer 1

[Extended sugerencia, publicado como respuesta, porque difícil de manejar como un comentario]

Considere la posibilidad de un vértice $v$ en su plano gráfico, por lo $\deg(v)\le4$.

Si $v$ $3$ o de pocos vecinos, hay en la mayoría de las $3$ colores adyacentes a $v$, por lo que podemos elegir el cuarto color para $v$.

Supongamos $v$ $4$ vecinos. Sólo estamos en problemas si todos los $4$ vecinos tienen diferentes colores. Pero eso es sólo un problema posible si todos los $4$ vecinos tienen un grado $4$ (de lo contrario, si uno de los vecinos había grado $\le 3$, se podía ignorarlo, color $v$, luego recolour el vecino de arriba).

Por lo que cualquier posible problema se reduce a tener $\deg(v)=4$, con todos los $4$ vecinos tener grado $4$, y no ser capaz de recolour. Puede usted pensar en una forma de traer a $K_5$ en el argumento? ¿Qué sabe usted acerca de la $K_5$ y grafos planares?

Edit: Mientras que las declaraciones anteriores son verdaderas, la prueba de que yo había esbozado en mi cabeza no funciona.

Answer 2

Elegir un vértice $v$ $G$ y de manera inductiva $4$color $G - v$. Si los vecinos de $v$ no representan a todos los $4$ clases de color, elija $v$'s de color para crear una normativa $4$colorear de $G$.

De lo contrario, cada una de las $v$'s de los vecinos es de color de un color diferente, y supongo que están etiquetados $v_1,v_2,v_3,v_4$ de las agujas del reloj en un plano de dibujo de $G$.

Ahora, tratamos de cambiar $v_1$'s de color para que coincida $v_3$'s, la propagación de cualquiera de los obligados cambios de color a través de la gráfica. Si esto es posible, entonces podemos color $v$ $v_1$'s de color original. Si no es posible, entonces hay una alternancia de ruta de los colores de $v_1$ $v_3$ conectar $v_1$$v_3$. Ya que la ruta se cierra una curva simple separación de $v_2$$v_4$, podemos intercambiar $v_2$'s de color a $v_4$'s sin problema, la creación de un marco jurídico $4$colorear de $G$.