Teorema de los 4 colores equivalente a que los planos cúbicos sin puentes son coloreables en 3 aristas

Question

Para seguir en [ ¿Cómo demostrar el teorema de Tait de que el grafo cúbico sin puentes es coloreable en 3 aristas?

El teorema de los cuatro colores es equivalente a la afirmación de que todo grafo cúbico planar sin puentes es coloreable en 3 aristas.

No estoy de acuerdo con la solución que se da (Como se indica en mi comentario). Los enlaces proporcionados no demuestran la equivalencia. Demuestra 1) a partir del teorema de los 4 colores, cómo construir una coloración de 3 aristas para un grafo cúbico sin puentes 2) a partir de una coloración de 3 aristas, cómo construir una coloración de 4 caras para el mismo gráfico

El teorema de Tait es mucho más potente. Si puedo colorear con 3 aristas cualquier gráfico plano sin puentes cúbicos, entonces puedo colorear con 4 aristas CUALQUIER gráfico plano (no sólo el plano sin puentes cúbicos).

Alguna idea de cómo demostrar la equivalencia. No puedo encontrar el documento original de Tait. Muchas referencias pero nunca la prueba real. La implicación 4CT $\Rightarrow$ La coloración de 3 aristas para el grafo cúbico planar sin puentes es fácil. La otra implicación es la que falta : $$ \{ \forall G, \text{ cubic, planar, bridgeless}, \exists \text{ a 3-edge coloring}\}$$ $$\Rightarrow$$ $$\{\forall G, \text{ planar,} \ \exists \text{a 4-vertex-coloring}\}$$

Answer 1

Supongamos que queremos colorear en 4 colores los vértices de un grafo plano.

Podemos suponer que es sencillo, porque los bucles están prohibidos y las aristas múltiples no afectan a la coloración.

Podemos suponer que se trata de un grafo plano máximo (es decir, una triangulación plana), porque añadir más aristas para triangular el grafo sólo dificulta el problema.

Todas las triangulaciones planas con al menos 4 vértices están conectadas por 3.

En lugar de colorear los vértices de este gráfico, podemos colorear las caras de su dual. El dual es otro gráfico plano. Es cúbico (porque empezamos con una triangulación) y tiene 3 conexiones (porque es el dual de un grafo plano simple de 3 conexiones), así que en particular no tiene puentes.

Así que hemos reducido el problema a colorear las caras de un grafo cúbico planar sin puentes, que es el tipo de grafo al que se aplica el teorema de Tait.

Answer 2

¿Por qué dices que la explicación del enlace no demuestra la equivalencia? Puedes decidir colorear las caras del mapa O puedes colorear las aristas del mismo mapa. Una vez que hayas terminado de colorear una u otra (las caras o las aristas) puedes cambiar a la otra de la forma descrita en el enlace. La dificultad de tres colorear las aristas o de cuatro colorear las caras es la misma. Como una de ellas ya está probada la otra también lo está.

Sobre el teorema de Tait, no hay ningún teorema de Tait, al menos no sobre cuatro coloraciones.

La equivalencia sólo dice que para un mismo mapa (no cualquier mapa) si se encuentra una coloración (caras de aristas) se puede pasar a la otra coloración, no dice que sea más fácil encontrar una u otra coloración. Para pasar de una coloración a la otra (relacionada con el mismo mapa) el algoritmo se describe en el enlace. El algoritmo es la prueba de la equivalencia.

ACTUALIZACIÓN (25/Ene/2019): La prueba debería estar aquí:

• P.G. Tait, "On the colouring of maps", Proceedings of the Royal Society de Edimburgo, Sección A, 10: 501-503, 1878-1880.
  • https://www.cambridge.org/core/journals/proceedings-of-the-royal-society-of-edinburgh/article/4-on-the-colouring-of-maps/6385395D337371EE9ED16C6AA6694AC0