Teorema de los cinco colores

El teorema de los cinco colores es una versión debilitada del teorema de los cuatro colores : los vértices de cualquier gráfico plano se pueden colorear en cinco colores para que dos vértices adyacentes sean de diferentes colores (este método de coloreado se llama correcto en matemáticas), o , lo que es lo mismo, el gráfico plano del número cromático como máximo 5. Probado a finales del siglo XIX por Percy Heawood .

Prueba

A diferencia del teorema de los cuatro colores, la prueba es bastante compacta. Se lleva a cabo por inducción sobre el número de vértices del gráfico. La base de la inducción es el hecho de que, para , uno puede simplemente colorear los vértices con diferentes colores. ${\ estilo de visualización V <6}$

Para un paso inductivo, se muestra que si para un gráfico de un vértice todos los gráficos planos con vértices se pueden colorear correctamente con 5 colores, entonces el gráfico en sí se puede colorear con 5 colores. Para ello, usamos el corolario de la fórmula de Euler de que en un grafo plano hay un vértice de grado menor que . Como el gráfico está coloreado de la manera correcta, hay dos opciones posibles: 1) si el grado es menor o si algunos dos vértices vecinos están coloreados del mismo color (en este caso, hay un color en el que ninguno de los vértices vecinos está coloreado). coloreado , y luego puede pintar con este color, y la coloración será correcta) 2) el grado del vértice es igual y todos los vértices adyacentes están coloreados en diferentes colores. $GRAMO$ ${\ estilo de visualización V+1}$ $V$ $tu$ $6$ ${\displaystyle G\setminus \{u\))$ $5$ $tu$ $5$ $tu$ $tu$ $tu$ $tu$ $5$

Para la segunda opción, se numeran cinco vértices adyacentes en el orden de pasar por alto los bordes salientes correspondientes en el sentido de las agujas del reloj: ; for denota el color del vértice ; un subgráfico de un gráfico sin se define como un subgráfico que contiene todos los vértices coloreados por colores de vértice y . Se consideran los dos casos siguientes: $tu$ ${\displaystyle v_{1},v_{2},v_{3},v_{4},v_{5))$ $c_{yo}$ $v_{i}$ ${\ Displaystyle H_ {ij}}$ $GRAMO$ $tu$ $v_{i}$ $v_{j}$

1. Los vértices y se encuentran en diferentes componentes conexas del gráfico . En este caso, es posible volver a colorear los vértices del mismo componente que , de la siguiente manera: volver a colorear todos los vértices de color a color y todos los vértices de color a color . La coloración del gráfico sin seguirá siendo correcta, pero ahora el vértice se coloreará con el color y no con , lo que significa que puede colorear el vértice con el color y obtener la coloración requerida del gráfico . $v_{1}$ $v_{3}$ ${\ estilo de visualización H_ {13}}$ $v_{1}$ $c_{1}$ $c_{3}$ $c_{3}$ $c_{1}$ $GRAMO$ $tu$ $v_{1}$ $c_{3}$ $c_{1}$ $tu$ $c_{1}$ $GRAMO$

2. Los vértices y se encuentran en la misma componente conexa del gráfico . Entonces entre los vértices y hay un camino en el gráfico . Junto con el vértice y las aristas , este camino también forma un ciclo . Dado que el gráfico es plano y es un ciclo que no se interseca a sí mismo, entonces, de acuerdo con el teorema de Jordan , divide el plano en componentes conexas (externa e interna), y los puntos y estarán en diferentes componentes, y por lo tanto habrá no hay camino de a en el gráfico . Entonces y están en diferentes componentes conexas del gráfico y, de manera similar al razonamiento del Caso 1, podemos volver a colorear los vértices de la misma componente conexa del gráfico como , de la siguiente manera: todos los vértices de color se vuelven a colorear con el color y todos los vértices del color se vuelven a colorear al color , y luego el vértice se vuelve a colorear al color y obtener el color deseado del gráfico . $v_{1}$ $v_{3}$ ${\ estilo de visualización H_ {13}}$ $v_{1}$ $v_{3}$ ${\ estilo de visualización H_ {13}}$ $tu$ ${\ estilo de visualización (v_ {3}, u)}$ ${\ estilo de visualización (u, v_ {1})}$ ${\ estilo de visualización C_ {13}}$ $GRAMO$ ${\ estilo de visualización C_ {13}}$ ${\ estilo de visualización C_ {13}}$ $2$ $v_{2}$ ${\ Displaystyle v_ {4}}$ $v_{2}$ ${\ Displaystyle v_ {4}}$ ${\ Displaystyle H_ {24}}$ $v_{2}$ ${\ Displaystyle v_ {4}}$ ${\ Displaystyle H_ {24}}$ ${\ Displaystyle H_ {24}}$ $v_{2}$ $c_{2}$ $c_{4}$ $c_{4}$ $c_{2}$ $tu$ $c_{2}$ $GRAMO$