Teorema de los cuatro colores: definición, historia y demostración

Intuitivamente, el teorema de los cuatro colores puede enunciarse como "dada una separación cualquiera de un plano en regiones contiguas, llamada mapa, las regiones pueden colorearse utilizando como máximo cuatro colores de manera que ninguna región adyacente tenga el mismo color". Para poder resolver correctamente el problema, es necesario aclarar algunos aspectos: En primer lugar, hay que ignorar todos los puntos que pertenecen a tres o más países. En segundo lugar, los mapas extraños con regiones de área finita y perímetro infinito pueden requerir más de cuatro colores.

A efectos del teorema, cada "país" tiene que ser una región simplemente conectada, o contigua. En el mundo real, esto no es cierto: Alaska como parte de Estados Unidos, Najchiván como parte de Azerbaiyán y Kaliningrado como parte de Rusia no son contiguos. Dado que el territorio de un determinado país debe ser del mismo color, cuatro colores pueden no ser suficientes. Por ejemplo, considere un mapa simplificado, como el que se muestra a la izquierda: En este mapa, las dos regiones etiquetadas como A pertenecen al mismo país, y deben ser del mismo color. Este mapa requiere entonces cinco colores, ya que las dos regiones A son contiguas a otras cuatro regiones, cada una de las cuales es contigua a todas las demás. Si A tuviera sólo tres regiones, podrían necesitarse seis o más colores. De este modo, es posible hacer mapas que necesiten un número arbitrario de colores. Una construcción similar se aplica también si se utiliza un único color para todas las masas de agua, como es habitual en los mapas reales.

Una versión del teorema más fácil de enunciar utiliza la teoría de los grafos. El conjunto de regiones de un mapa puede representarse de forma más abstracta como un grafo no dirigido que tiene un vértice por cada región y una arista por cada par de regiones que comparten un segmento límite. Este grafo es plano: puede dibujarse en el plano sin cruces colocando cada vértice en una ubicación elegida arbitrariamente dentro de la región a la que corresponde, y dibujando las aristas como curvas que conducen sin cruces dentro de cada región desde la ubicación del vértice hasta cada punto límite compartido de la región. A la inversa, cualquier gráfico plano puede formarse a partir de un mapa de esta manera. En la terminología de la teoría de los grafos, el teorema de los cuatro colores afirma que los vértices de todo grafo planar pueden colorearse con un máximo de cuatro colores, de modo que no hay dos vértices adyacentes que tengan el mismo color, o para abreviar, "todo grafo planar es cuatricolorable" (Thomas 1998, p. 849; Wilson 2002).

La primera persona que nombró el problema fue Francis Guthrie, en 1852. Por aquel entonces era un estudiante de derecho en Inglaterra. Descubrió que necesitaba al menos cuatro colores para colorear un mapa de los condados de Inglaterra. Augustus de Morgan discutió por primera vez el problema, en una carta que escribió a Rowan Hamliton en agosto de 1852. En la carta, de Morgan se pregunta si cuatro colores son realmente suficientes para colorear un mapa, de forma que los países que están uno al lado del otro reciban colores diferentes.

El matemático inglés Arthur Cayley presentó el problema a la sociedad matemática de Londres, en 1878. Al cabo de un año, Alfred Kempe encontró lo que parecía una prueba del problema. Once años después, en 1890, Percy Heawood demostró que la prueba de Alfred era errónea. Peter Guthrie Tait presentó otro intento de prueba en 1880. Se necesitaron once años para demostrar que la prueba de Tait tampoco funcionaba. En 1891, Julius Petersen pudo demostrarlo. Cuando falsificó la prueba de Cayley, Kempe también mostró una prueba para un problema que llamó Teorema de los cinco colores. El teorema dice que cualquier mapa de este tipo puede ser coloreado con no más de cinco colores. Hay dos restricciones: La primera es que cualquier país es contiguo, no hay exclaves. La segunda restricción es que los países deben tener una frontera común; si sólo se tocan en un punto, pueden ser coloreados con el mismo color. Aunque la prueba de Kempe era errónea, utilizó algunas de las ideas que más tarde permitirían una prueba correcta.

En los años 60 y 70, Heinrich Heesch desarrolló un primer esbozo de prueba por ordenador. Kenneth Appel y Wolfgang Haken mejoraron este esbozo en 1976 (Robertson et al. 1996). Consiguieron reducir el número de casos que había que probar a 1936; se hizo una versión posterior que se basaba en probar sólo 1476 casos. Cada caso debía ser probado por un ordenador (Appel & Haken 1977) harv error: objetivos múltiples (2×): CITEREFAppelHaken1977 (ayuda).

En 1996, Neil Robertson, Daniel Sanders, Paul Seymour y Robin Thomas mejoraron el método y redujeron el número de casos a probar a 663. De nuevo, cada caso debía ser probado por ordenador.

En 2005, Georges Gonthier y Benjamin Werner desarrollaron una prueba formal. Esto supuso una mejora, ya que permitió utilizar, por primera vez, un software de demostración de teoremas. El software utilizado se llama Coq.

El teorema de los cuatro colores es el primer gran problema matemático que se demostró con la ayuda de un ordenador. Como la demostración no puede ser realizada por un humano, algunos matemáticos no la reconocieron como correcta. Para verificar la prueba, es necesario contar con un software y un hardware que funcionen correctamente para validar la prueba. Como la prueba se hizo por ordenador, tampoco es muy elegante.

El teorema de los cuatro colores ha sido notorio por atraer un gran número de pruebas y refutaciones falsas en su larga historia. Al principio, The New York Times se negó a informar sobre la prueba de Appel-Haken. El periódico lo hizo por una cuestión de política; temía que la prueba se demostrara falsa como las anteriores (Wilson 2002, p. 209). Algunas pruebas tardaron mucho tiempo, hasta que pudieron ser falsificadas: En el caso de las pruebas de Kempe y Tait, falsificarlas llevó más de una década.

Los contraejemplos más sencillos suelen tratar de crear una región que toque a todas las demás. Esto obliga a colorear las regiones restantes con sólo tres colores. Como el teorema de los cuatro colores es cierto, esto siempre es posible; sin embargo, como la persona que dibuja el mapa está centrada en la única región grande, no se da cuenta de que las regiones restantes pueden, de hecho, colorearse con tres colores.

Este truco puede generalizarse: Si los colores de algunas regiones de un mapa se eligen de antemano, resulta imposible colorear las regiones restantes de forma que en total sólo se utilicen cuatro colores. Alguien que verifique el contraejemplo puede no pensar que puede ser necesario cambiar el color de estas regiones. Esto hará que el contraejemplo parezca válido, aunque no lo sea.

Tal vez un efecto que subyace a este error común es el hecho de que la restricción de color no es transitiva: una región sólo tiene que ser coloreada de forma diferente a las regiones que toca directamente, no a las regiones que tocan a las que toca. Si esta fuera la restricción, los grafos planares requerirían un número arbitrario de colores.

Otras falsas refutaciones violan los supuestos del teorema de formas inesperadas, como el uso de una región que tiene múltiples partes desconectadas, o no permitir que regiones del mismo color se toquen en un punto.

En la vida real, muchos países tienen exclaves o colonias. Dado que pertenecen al país, es necesario colorearlos con el mismo color que el país matriz. Esto significa que, normalmente, se necesitan más de cuatro colores para colorear un mapa de este tipo. Cuando los matemáticos hablan del gráfico asociado al problema, dicen que no es plano. Aunque es fácil comprobar si un gráfico es planar, encontrar el menor número de colores necesarios para colorearlo es muy difícil. Es NP-completo, que es uno de los problemas más difíciles que existen. El menor número de colores necesarios para colorear un grafo se conoce como su número cromático. Muchos de los problemas que se plantean al intentar resolver el teorema de los cuatro colores están relacionados con las matemáticas discretas. Por esta razón, se suelen utilizar métodos de la topología algebraica.

El teorema de los cuatro colores requiere que el "mapa" esté en una superficie plana, lo que los matemáticos llaman un plano. En 1890, Percy John Heawood creó lo que hoy se llama la conjetura de Heawood: Plantea la misma cuestión que el teorema de los cuatro colores, pero para cualquier objeto topológico. Como ejemplo, un toro puede ser coloreado con un máximo de siete colores. La conjetura de Heawood da una fórmula que funciona para todos esos objetos, excepto la botella de Klein.