TEOREMA DE LOS CUATRO COLORES

Es un teorema sobre la coloración de grafos y que dice lo siguiente[1]:

Dado cualquier mapa geográfico este puede ser coloreado con 4 colores diferentes de forma que no queden regiones adyacentes con el mismo color.

Observe el mapa de la Figura 1.

https://upload.wikimedia.org/wikipedia/commons/thumb/0/0a/Four_color_world_map.svg/940px-Four_color_world_map.svg.png

Figura 1

Tres colores no son suficientes para colorear mapas simples, en algunos casos es necesario un cuarto color adicional, cuando una región a colorear queda encerrada por un número impar de regiones que se tocan formando un ciclo.

Vea ahora el mapa de la Figura 2.

https://upload.wikimedia.org/wikipedia/commons/thumb/8/8a/Four_Colour_Map_Example.svg/300px-Four_Colour_Map_Example.svg.png

Figura 2

Este problema fue planteado por primera vez, por el estudiante Francis Guthrie en 1852, alumno de Augustus De Morgan, el cual se hizo famosos cuando Arthur Cayley en 1878 mencionó que lo había abordado.

El problema fue transmitido a Sir Wlliam Rowan Hamilton el cual no pudo demostrarlo y en 1879 Alfred Bray Kempe anunció que tenía una demostración, pero en 1890 Heawood encontró un error en ésta; aunque si proporcionó algunas herramientas básicas utilizadas posteriormente para demostrarlo y no fue hasta que Kenneth Appel y Wolfgang Haken lo resolvieron en 1970, quienes utilizaron una computadora; generándose así una polémica en el ambiente matemático ya que no fue aceptada por todos, debido a la gran cantidad de detalles que llevaba, por lo que era necesario hacer uso de la computadora, pues la mente humana se veía imposibilitada para verificarlo personalmente. Además de restarle elegancia, la cual es muy valorada por los matemáticos al proponer soluciones ingeniosas y simples, y no documentos plagados de procedimientos repetitivos, largos y tediosos. Finalmente en el año 1996 Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas del Georgia Institute of Technology publicaron una prueba que no usaba una computadora y así la polémica desapareció[2].

Intente colorear los siguientes mapas con solamente tres colores sin que dos regiones que tienen frontera en común tengan el mismo color (ver Figuras 3, 4 y 5).

Figura 3

Figura 4

Figura 5

 

Referencias:

  1. Ver: https://es.wikipedia.org/wiki/Teorema_de_los_cuatro_colores
  2. Ver: https://www.um.es/docencia/pherrero/mathis/colores/4colores.htm