El teorema de los cuatro colores: la teoría de grafos al servicio del coloreado de mapas

Seguro que muchos de los lectores de este blog conocen el teorema que da título a esta entrada. El teorema de los cuatro colores es un importante (y bastante conocido) resultado de teoría de grafos que, aunque ha sido citado ya por aquí, no tenía un post dedicado a él. Creo que hoy, después de conocer el fallecimiento de Kenneth Appel (uno de los matemáticos que lo demostró) el pasado 19 de abril, es un buen día para ello.

Comencemos con algo de la historia del problema. A mediados del siglo XIX Francis Guthrie se dio cuenta mientras coloreaba un mapa de los condados de Inglaterra de que necesitaba al menos cuatro colores para que se cumpliera la condición de que dos regiones con frontera común tuvieran colores distintos (si dos regiones se tocan en un único punto se entiende que no tienen frontera común). Francis le comentó el tema a su hermano Frederick, que a su vez se lo planteó a Augustus de Morgan (profesor suyo en un curso de matemáticas en aquel momento), que aunque no supo responderle se encargo de difundir el asunto entre otros matemáticos. En 1878 Arthur Cayley lo presenta formalmente a la London Mathematical Society y así el problema queda abierto con un enunciado como éste:

Todo mapa plano puede colorearse con, como máximo, cuatro colores con la condición de que regiones con frontera común tengan colores distintos.

El años siguiente, 1879, es una fecha importante en relación con este problema. Ese año Alfred Kempe publica una demostración del mismo. En efecto parece ser que con cuatro colores era suficiente y el problema estaba resuelto…

…y así fue hasta 1890, año en el que Percy Heawood encontró un error insalvable en la demostración de Kempe, por lo que el problema volvía a estar abierto. A partir de aquí muchos matemáticos (entre ellos el propio Heawood) atacaron el problema, pero ninguno de ellos consiguió dar con la tecla…y nunca mejor dicho.

Pero todos esos intentos fallidos no fueron en vano. Por el camino quedaron demostraciones de que para colorear un mapa dibujado en un toro hacen falta, como máximo, siete colores, y que para colorear uno mapa en una banda de Möbius hacen falta, a lo sumo, seis colores. También se demostró que cinco colores eran suficientes para un mapa plano. Pero parecía que todos los mapas podían colorearse con cuatro, que no nos hacían falta esos cinco…

Por cierto, hemos comentado al principio que este problema pertenece a la teoría de grafos, pero no hemos dicho cómo relacionar mapas con grafos. Lo que se hace a partir de cada mapa plano es calcular su grafo dual, que se construye asignando un vértice a cada región y uniendo dos vértices con una arista si en el mapa las dos regiones correspondientes a dichos vértices tenían frontera común. Por ejemplo, este mapa de Castilla-La Mancha (que he tomado de aquí)

tendría como grafo dual al siguiente grafo:

De esta forma el problema queda planteado de la siguiente forma:

¿Es cierto que los vértices de todo grafo plano pueden colorearse con, a lo sumo, cuatro colores de forma que dos vértices unidos por una arista tengan colores distintos?

Por ejemplo, el mapa anterior (y, por tanto, también su grafo dual) puede colorearse con, en este caso, tres colores:

Con todo esto entramos en el siglo XX y sobre 1950 se comienza a pensar que los ordenadores podrían ser de gran ayuda en este problema. El matemático alemán Heinrich Heesch fue uno de los pioneros en este sentido, y sus investigaciones acabaron siendo fundamentales para el desenlace del asunto. Pero los auténticos protagonistas de la demostración del teorema de los cuatro colores son Kenneth Appel y Wolfgang Haken. Ellos fueron los que, en 1976, anunciaron que «Cuatro colores son suficientes». La demostración que presentaron no es de las, digamos, «habituales», ya que una buena parte de la misma se realizó con ayuda del ordenador. Más adelante se presentaron mejoras a la demostración de Appel y Haken, y hasta hay alguna propuesta que no utiliza ordenador (que, hasta donde yo sé, no está confirmada como correcta), pero ellos fueron los primeros.

En la actualidad, la opinión más extendida es que el teorema de los cuatro colores está demostrado, aunque quedan escépticos que consideran que no es «lícito» utilizar el ordenador de la forma en la que se hace en estas demostraciones. Sobre todas ellas tenéis más información en el pdf de Marta Macho que enlazo al final de esta entrada.

Fallecimiento de Kenneth Appel

Como decía al comienzo de esta entrada, me he decidido a escribir de este teorema después de enterarme del fallecimiento de Kenneth Appel gracias a este post de Marta Macho en ZTFNews. Kenneth Appel, matemático estadounidense, falleció el pasado 19 de abril a la edad de 80 años. Aunque hizo alguna aportación a la teoría de grupos, se le conoce principalmente por su demostración junto a Wolfgang Haken del teorema de los cuatro colores. En este obituario (en inglés) tenéis más información.

Parece entonces que ha quedado demostrado que todo mapa plano puede colorearse con, como mucho, cuatro colores de forma que regiones con frontera común tengan colores distintos. ¿Todos? ¿Hasta éste?

Este mapa fue propuesto por Martin Gardner como mapa que no podía colorearse con cuatro colores…un 1 de abril, día de los inocentes para el mundo anglosajón. Hablé sobre ello en este post, en el que propuse algunas otras inocentadas con las que el propio Gardner acompañó a la de este mapa. Evidentemente es falso que hagan falta cinco colores. Gardner recibió cartas con diversas formas de colorear el mapa con cuatro colores. Aquí os dejo una de Stan Wagon:

Y para terminar os dejo un entretenimiento. Si todo mapa plano puede colorearse con, como mucho, cuatro colores con la condición comentada antes, ¿por qué no plantearlo como un juego? ¿Serías capaz de colorear cualquier mapa plano que te dibujen con sólo cuatro colores? Demuéstralo jugando a Flood Fill, un adictivo juego que vi hace unos meses en Microsiervos en el que el objetivo es, precisamente, colorear con como mucho cuatro colores el mapa que nos proponen en cada uno de sus niveles. Al principio es fácil, pero conforme la cosa avanza el nivel de dificultad va subiendo. Por ejemplo, aquí tenéis una forma de pasarse el nivel 10:

Repito, es adictivo, mucho cuidado con él.

Fuentes y más información:

• Mapas del metro y redes neuronales, de Claudi Alsina.
• El teorema de los cuatro colores en la Wikipedia en español.
• Presentación de Marta Macho sobre el teorema de los cuatro colores (pdf).
• ¿Por qué sólo cuatro colores?, post de Clara Grima en Naukas sobre el teorema de los cuatro colores en el que además del contarnos cosas sobre el propio resultado también nos muestra algunas de sus aplicaciones.

Cuarta aportación a la Edición 4.123 del Carnaval de Matemáticas, que organiza el blog Eulerianos.