Matemáticas explicadas con claridad

El teorema de los cuatro colores, explicado

Cuatro colores bastan para cualquier mapa del mundo - eso es lo que afirma el teorema de los cuatro colores. Una afirmación que cabe en una sola frase, pero que tardó 124 años y, al final, un ordenador en demostrarse. Esta es la historia completa: qué dice realmente el teorema, por qué resistió tanto tiempo sin demostración, cómo se logró finalmente la prueba - y dónde deja de cumplirse.

Cartographer convierte este mismo teorema en un juego - 120 islas dibujadas a mano, las primeras 10 gratis.

¿Qué dice el teorema de los cuatro colores?

El teorema de los cuatro colores es una de las afirmaciones más compactas de las matemáticas: cualquier mapa puede colorearse con un máximo de cuatro colores de modo que dos regiones vecinas nunca compartan el mismo color. No importa cuántos países tenga el mapa ni lo retorcidas que sean sus fronteras - cuatro colores siempre bastan.

Dos palabras de esa frase pesan más de lo que parece a primera vista. Dos regiones son vecinas solo si comparten una verdadera línea fronteriza - un simple punto de contacto no cuenta. Y cada región tiene que ser conexa: un país formado por dos partes separadas no cuenta como una sola región. Ambas condiciones parecen letra pequeña, pero son la razón por la que el teorema se puede demostrar - y, como se explica más adelante, también la razón por la que no encaja del todo con algunos mapas reales.

En términos matemáticos, el teorema de los cuatro colores es en realidad un enunciado sobre grafos, no sobre mapas: cualquier mapa puede traducirse a un llamado grafo planar, convirtiendo cada región en un punto y cada frontera compartida en una línea que conecta dos puntos. El teorema dice entonces: todo grafo planar puede colorearse con un máximo de cuatro colores de modo que dos puntos unidos por una línea nunca compartan color. Los mapas son solo la versión más intuitiva de esta afirmación más abstracta y general.

¿Por qué no es evidente el teorema de los cuatro colores?

Que tres colores a veces no bastan se demuestra en segundos: tres regiones que se tocan todas entre sí necesitan tres colores distintos. Sería natural suponer que ese truco se puede repetir sin límite - cinco regiones que se tocan entre sí para cinco colores, seis para seis, y así sin techo alguno. Pero eso no es lo que ocurre. A partir de cierto punto, la simple geometría de una superficie plana impide que un número arbitrario de regiones se toquen todas entre sí - y ese límite resulta ser cuatro. El teorema de los cuatro colores es la afirmación de que ese límite no solo vale para mapas pequeños y sencillos, sino para cualquier mapa imaginable, por complicado que sea. Ese salto de "cierto en todos los casos examinados hasta ahora" a "cierto en todo caso concebible, para siempre" es lo que convierte una observación en un teorema - y lo que convirtió a este en un problema abierto durante 124 años.

La historia del teorema de los cuatro colores

La conjetura nació de un estudiante: en 1852, el londinense Francis Guthrie estaba coloreando un mapa de los condados ingleses y notó que nunca necesitaba más de cuatro colores, por más que trazara las fronteras. Su hermano Frederick llevó la pregunta al matemático Augustus De Morgan, quien ese mismo día - el 23 de octubre de 1852 - la trasladó en una carta a William Rowan Hamilton. Hamilton no mostró ningún interés, pero De Morgan no dejó el asunto y siguió planteándolo en los círculos matemáticos de Londres.

En 1878, Arthur Cayley presentó la pregunta, aún sin resolver, ante la London Mathematical Society. Un año después, el abogado y matemático aficionado Alfred Kempe publicó una demostración que se dio por válida durante once años. El método de Kempe - hoy conocido como cadenas de Kempe - es en sí mismo una idea elegante: se toman dos de los cuatro colores y se sigue la cadena conexa de regiones que alternan solo entre esos dos colores. Si esa cadena puede cortarse en algún punto, los dos colores de una parte de la cadena pueden intercambiarse sin generar ningún conflicto - liberando así el cuarto color justo donde hacía falta. En paralelo, Peter Guthrie Tait intentó también su propia demostración en 1880.

En 1890, Percy Heawood encontró el fallo en el argumento de Kempe: en ciertas configuraciones, dos cadenas no pueden intercambiarse de forma independiente sin abrir un nuevo conflicto en otro punto. La demostración de Kempe quedó refutada - el teorema de los cuatro colores volvía a estar abierto. De entre los escombros, Heawood rescató el teorema de los cinco colores: con la técnica de cadenas de Kempe se puede demostrar por completo, a mano, que cinco colores siempre bastan para cualquier mapa. Solo el último paso decisivo, de cinco a cuatro, seguía sin demostrarse. En 1891, Julius Petersen refutó además el intento de Tait de 1880. Durante casi un siglo más, el teorema de los cuatro colores siguió siendo una conjetura abierta.

1.476 patrones de mapa son cosa de ordenador. Una sola isla, en cambio, se resuelve bien a mano - en Cartographer hay 120 esperando.

Probar gratis

La demostración de 1976: ordenador contra papel y lápiz

El avance definitivo llegó en 1976, de la mano de Kenneth Appel y Wolfgang Haken en la Universidad de Illinois - pero no sobre el papel. Su estrategia sigue un patrón que ya apuntaba Kempe: suponer que existe un mapa que viola el teorema y elegir, entre todos los posibles contraejemplos, el más pequeño. Luego se demuestra que ese contraejemplo mínimo es imposible - y, por tanto, también lo es cualquier contraejemplo mayor, ya que uno mayor siempre podría reducirse a uno menor.

La clave está en encontrar un conjunto inevitable de configuraciones reducibles: una lista de patrones de mapa de los que al menos uno tiene que aparecer en todo contraejemplo mínimo (inevitable), y de los que cada uno se puede demostrar individualmente que es imposible (reducible). Para hallar esa lista, Appel y Haken usaron el llamado método de descarga: a cada región se le asigna una carga inicial según su número de vecinos, y esa carga se redistribuye entre regiones vecinas siguiendo reglas fijas - de forma parecida a una red eléctrica. Al final queda claro qué regiones tienen que pertenecer necesariamente a una de las configuraciones reducibles.

Al final quedaron 1.936 configuraciones, reducidas después a 1.476 - demasiadas para revisarlas a mano. Appel y Haken pusieron a un ordenador a calcular durante unas 1.200 horas. El resultado: el teorema de los cuatro colores es cierto. Pero ningún matemático pudo ya seguir la demostración de principio a fin a mano - no era demasiado difícil para una persona, simplemente demasiado larga.

„Four colors suffice.“Matasellos usado durante años por el departamento de matemáticas de la Universidad de Illinois tras 1976

Aquello desató una auténtica controversia en la comunidad matemática. ¿Seguía siendo una demostración algo que ya no se podía leer, solo ejecutar? En 1989, Appel y Haken publicaron una versión completa de unas 400 páginas. En 1997, Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas redujeron el número de casos necesarios a 633 - la demostración se simplificó, pero siguió dependiendo de un ordenador. La confirmación definitiva llegó recién en 2005: Georges Gonthier y Benjamin Werner hicieron revisar toda la demostración de nuevo con un llamado asistente de demostración llamado Coq - un programa que verifica formalmente cada paso lógico, sin dejar el menor resquicio para la duda.

Por qué nadie puede comprobar la demostración a mano

La diferencia entre el teorema de los cuatro colores y el teorema de los cinco colores deja claro de qué se trata todo esto. El teorema de los cinco colores - la afirmación más débil de que cinco colores siempre bastan - se puede demostrar por completo a mano, con la técnica de cadenas de Kempe, en pocas páginas, y cualquier estudiante de matemáticas puede seguirlo. En el teorema de los cuatro colores, en cambio, el número de casos que deja pendientes el método de descarga es sencillamente demasiado grande para una mente humana - no demasiado complicado, sino demasiado extenso. Eso era algo completamente nuevo en 1976: la primera gran demostración matemática que dependía esencialmente de un ordenador. Hoy es algo habitual en muchas áreas de las matemáticas, pero el teorema de los cuatro colores fue el caso que obligó por primera vez a la comunidad a preguntarse en serio qué es realmente una demostración cuando ya ningún humano puede revisarla por completo.

Dónde el teorema de los cuatro colores llega a su límite

El teorema de los cuatro colores describe geometría pura - y en cuanto entran en juego países y fronteras reales, también muestra sus límites.

El teorema de los cuatro colores en la práctica: coloración de grafos

El teorema de los cuatro colores en sí es un enunciado sobre mapas y grafos planares - pero la idea que hay detrás, colorear un grafo de modo que los puntos conectados nunca compartan color, es una herramienta mucho más general de la informática conocida como coloración de grafos. En la planificación de horarios, por ejemplo, cada evento se convierte en un punto, y dos eventos se conectan cuando no pueden coincidir - porque, por ejemplo, los imparte el mismo profesor. Una coloración válida corresponde entonces a un horario sin choques, donde cada color representa una franja horaria. La asignación de registros en los compiladores, cuando las variables de un programa deben repartirse entre un número limitado de registros del procesador, es en el fondo el mismo problema. A diferencia de los mapas, sin embargo, estos grafos casi nunca son planares - así que el límite de cuatro colores no se aplica ahí, y a menudo hacen falta muchos más. Lo que queda es la idea que hizo famoso al teorema de los cuatro colores.

Prueba tú mismo el teorema de los cuatro colores

Cartographer convierte el teorema de los cuatro colores en un juego: 120 mapas de islas dibujados a mano, todos gobernados por esta única regla - los vecinos nunca pueden compartir color. Las primeras 10 son gratis, y hay una demo jugable directamente en el navegador.

Jugar la demo

Preguntas frecuentes sobre el teorema de los cuatro colores