El teorema de los cuatro
colores. Algo de historia y una anécdota.
El problema
El llamado «teorema de los cuatro
colores» establece que bastan cuatro colores distintos para colorear un mapa
cualquiera en un plano, de tal modo que cualesquiera dos regiones que compartan
una frontera común ―una línea, el punto no cuenta― tengan asignados
colores diferentes. La historia de esta conjetura, finalmente confirmada, es lo
bastante alambicada como para merecer una breve reseña.
Este problema fue inicialmente
conocido con el nombre de «problema de Guthrie», puesto que fue Francis Guthrie,
a la sazón estudiante en el University College de Londres, quien primero lo dio
a conocer, el año 1853. No satisfecho con las pruebas que trató de desarrollar,
habló del problema a su hermano Frederick, el cual lo comunicó a su vez a su
instructor, el famoso Augustus De Morgan. En una carta fechada el 23 de octubre
de 1852, De Morgan mencionó el problema a Sir William Rowan Hamilton, el cual,
entreviendo probablemente la extrema dificultad del mismo, le contestó que no
tenía intención de considerarlo en un futuro próximo. Como es natural, De
Morgan habló con frecuencia de este problema con otros matemáticos. De hecho,
se cree que fue él mismo el autor de un artículo anónimo aparecido en el número
del 14 de abril de 1860 de la revista Athenaeum y que trata del problema de los
cuatro colores, siendo ésta la primera referencia publicada de dicha conjetura.
En la década de 1860 ya se tenía
constancia del problema en Norteamérica, donde atrajo el interés del filósofo
C. S. Pierce. El 13 de junio de 1878 el matemático Arthur Cayley preguntó si el
problema había sido resuelto, y poco después publicó un artículo sobre el asunto,
en el cual exponía las dificultades inherentes al mismo [A. Cayley, «On the
colourings of maps», Proc. Royal Geog.
Soc. 1 (1879), págs.
259-261].
El número del 17 de julio de 1879 de
la revista Nature anunciaba que el problema de los cuatro colores había sido
resuelto, en el sentido de confirmar la conjetura, por el abogado inglés Alfred
Bray Kempe. Su solución apareció en un artículo publicado en el ejemplar de la
revista American Journal of Mathematics de 1879. Así, el artículo de Kempe fue
la primera pretendida demostración de que las regiones de un grafo plano
cualquiera se pueden colorear con cuatro colores de forma que a regiones
adyacentes correspondan colores distintos.
Durante la década que siguió a la
publicación del artículo de Kempe el problema de los cuatro colores se
consideró resuelto. Por ese supuesto logro, Kempe fue nombrado Fellow de la
Royal Society, y presentó algunos perfeccionamientos de su prueba. Algo
después, P. G. Tait, de la Universidad de Edimburgo, describió otra pretendida
demostración. Lewis Carroll creó un juego para dos jugadores en el cual cada
uno de ellos diseñaba un mapa, sujeto a ciertas restricciones, que su oponente
debía colorear con cuatro colores, siendo ganador el que lo conseguía antes. En
1889, el Obispo de Londres, Frederick Temple, más tarde Arzobispo de
Canterbury, publicó su propia solución del problema de los cuatro colores en la
revista Journal of Education.
Pero en 1890 se comprobó que el
problema era mucho más rebelde de lo que parecía. Percy John Heawood anunció
haber descubierto un error en la demostración de Kempe, de tal gravedad que él
mismo no fue capaz de corregirlo [P. J. Heawood, «Map-colour theorem», Quart. J. Math. 24 (1890), págs. 332-339]. En su
artículo, Heawood proporcionó un ejemplo de un mapa que, a pesar de poderse
colorear fácilmente con cuatro colores, dejaba claro que la técnica de la
demostración de Kempe no tenía validez general. El mapa usado por Heawood tenía
18 regiones, que más tarde se comprobó que podían reducirse a 9. De pasada,
Heawood utilizó la técnica de la demostración de Kempe para probar que
cualquier mapa puede colorearse con cinco colores.
El problema de colorear mapas se
generaliza a superficies no planas. Heawood obtuvo una fórmula que establecía
el mínimo de colores necesarios para un mapa en una superficie cerrada
cualquiera, con la excepción del caso de la botella de Klein, para la cual la
fórmula de Heawood da el valor de siete, pero seis son bastantes para la tarea.
Para una superficie cerrada con una característica de Euler igual a n (el
problema de los cuatro colores es un problema de topología, en concreto de la
teoría de grafos), Heawood calculó el número mínimo de colores en
En el caso de un toro, para el que n
= 0, el número mínimo de colores es de 7. En el caso de la esfera es n = 0, de
modo que el número mínimo de colores es de cuatro. No se sabe con seguridad si
la fórmula de Heawood establece la cota inferior para el número de colores en
todos los casos, dejando aparte el de la botella de Klein.
A principios de la segunda mitad del
siglo XX fue posible demostrar que bastan seis colores para el caso de la clase
a la que pertenece el plano, y este número se redujo también fácilmente a
cinco, pero rebajar el número de colores a cuatro resultó ser un problema sumamente
difícil.
El teorema
El 21 de junio de 1976 Kenneth Appel
y Wolfgang Haken, de la Universidad de Illinois, anunciaron que, con la ayuda
de John Koch, habían resuelto el problema de los cuatro colores. No sorprende
que su pretensión fuera recibida con escepticismo, entre otras razones porque
la solución propuesta requería cientos de horas de cálculos mediante
computador. No obstante, dicha solución ha resistido el escrutinio y la prueba
del tiempo.
La singularidad del teorema
Debido a que parte de la prueba
consiste en un análisis exhaustivo de muchos casos discretos mediante
computador, algunos matemáticos no aceptan esta prueba como una demostración
rigurosa. Esta actitud hostil hacia teoremas cuya demostración descansa en
parte en una comprobación por computador se ha relajado posteriormente entre
los matemáticos, y actualmente se considera que el algoritmo del programa de
cálculo puede considerarse válido como parte de la prueba. El siguiente teorema
que se apoya en comprobaciones por computador es el correspondiente a la
conjetura de Kepler para el empaquetamiento de esferas, cuya demostración fue
anunciada por Hales y Ferguson en agosto de 1998.
Otras demostraciones
Una prueba potencialmente
independiente del teorema de los cuatro colores ha sido construida
recientemente por Robertson y otros (Robertson, Sanders, Seymour y Thomas,
desarrollada en 1996 y publicada en 1997).
En un encuentro científico que tuvo
lugar en Francia en diciembre de 2004, G. Gonthier de Microsoft Research de
Cambridge, Inglaterra, en un trabajo realizado conjuntamente con B. Werner de INRIA,
Francia, anunció la verificación de la demostración de Robertson y otros,
formulando el problema mediante el programa Coq de ecuaciones de tipo lógico, y
confirmaron la validez de cada uno de sus pasos (Devlin 2005, Knight 2005).
Una demostración sospechosamente
concisa, ya que consta solamente de 12 páginas, y que no ha sido verificada fue
propuesta por Cahit en el año 2004.
Figura 1
La anécdota: la broma de «April Fool» de Martin Gardner
Martin Gardner, editor durante
muchos años de la columna «Mathematical Games» de la revista Scientific
American, gastó en el número de abril de 1975 una broma de «April Fool»
(equivalente a nuestro día de los Santos Inocentes) pretendiendo que se había
demostrado que el mapa de 110 regiones ilustrado en la figura 1 requería
necesariamente cinco colores, constituyendo así un contraejemplo que invalidaba
la por entonces todavía conjetura de los cuatro colores. Sin embargo, el
coloreado reproducido más abajo y debido a Wagon (1998; 1999, pp. 535-536)
muestra claramente que este mapa puede colorearse con cuatro colores.
El propio Gardner, en el número de
agosto de 1998 de Scientific American, hace un recuento de 25 años de
colaboración con la revista, titulado «A Quarter-Century of Recreational
Mathematics (1956-1981)», y dedica un recuerdo especial a la broma de abril de
1975. Además de proponer seriamente el mapa que pretendidamente se había
demostrado que necesitaba de cinco colores, Gardner hacía tambalearse parte de
la ciencia: su artículo incluía una refutación de la teoría de la relatividad, la
revelación de que Leonardo había inventado el retrete que se limpia con el agua
de su cisterna, el supuestamente reciente descubrimiento de que el movimiento
de apertura de peón a cuatro torre de rey en ajedrez ganaba indefectiblemente la
partida, y que la base de los logaritmos naturales, el número e, elevado a la
potencia 
, da como resultado un número entero, 262 537 412 640 768 744. Cuenta el famoso
editor de la columna «Mathematical Games» que no le cabía duda de que todos los
lectores reconocerían la broma de «April Fool» en su aportación de ese mes,
pero que para pasmo suyo recibió centenares de cartas con el mapa coloreado con
cuatro colores, tarea que muchos lectores confesaban que les había llevado
varios días.
Más sobre la cuestión
En Carrollia- 65 Miguel Ángel Lerma
trata la extensión del teorema a grafos con un número infinito de regiones.
Nota acerca del April Fool’s Day
El día 1 de abril, conocido en los
países de habla inglesa como April Fool’s Day, equivale a nuestro día de los Santos
Inocentes del 28 de diciembre, y existe la misma costumbre de gastar bromas. El
origen de dicha costumbre parece ser muy antiguo y sus raíces no son claras. Aunque no parece muy fundada, una idea lo sitúa
en Francia y lo atribuye a los tiempos de la reforma gregoriana del calendario,
que trasladó el comienzo del año del día 1 de abril, hasta ese momento el
tradicional, al primero de enero; según dicha idea, los que se resistieron a
adoptar la nueva consigna eran tildados de tontos y objeto de todo tipo de bromas.
Y a todo esto, ¿qué fue de Francis
Guthrie?
El autor del problema que comentamos
se trasladó a Sudáfrica, en donde ejerció como profesor de matemáticas en el
South African College de Ciudad del Cabo (más tarde convertido en la
Universidad de Ciudad del Cabo). Fue también un botánico aficionado, un hobby
recompensado por la abundancia de flora indígena en la región. Tres raras
especies de flores tienen su nombre en recuerdo de Guthrie; las tres crecen en
el área de Bredarsdom, y son:
a) Cyrtanthus guthrieae, también
llamada Amaryllidaceae. Florece en marzo, antes de que aparezcan sus hojas.
b) Gladiolous guthriei, conocida
también con el nombre de Iridaceae. Florece en invierno (junio y julio). Tiene
un intenso aroma y es común en la zona de Pearly Beach.
c)
Homoglossum guthriei. Florece
en primavera (agosto-septiembre). Carece de aroma y se encuentra con
dificultad.
P. Crespo, mayo 2005