Teorema de los cuatro colores

Ejemplo de mapa coloreado con cuatro colores

Mapa del mundo coloreado de verde, amarillo, azul y rojo

En teoría de grafos, el teorema de los cuatro colores (o teorema de la minimalidad cromática) es un teorema sobre la coloración de grafos que establece lo siguiente:

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

Asumiendo que las regiones adyacentes comparten no solo un punto, sino todo un segmento de borde (frontera) en común.

Tres colores son suficientes para mapas simples, pero en algunos casos es necesario un cuarto color adicional, esto es, cuando una región a colorear queda encerrada por un número impar de regiones que se tocan formando un ciclo. El teorema de los cinco colores, cuya demostración es corta y elemental, establece que cinco colores son suficientes para colorear un mapa y fue probado en el siglo XIX por Heawood.​ Una serie de pruebas falsas y falsos contraejemplos han aparecido desde el primer enunciado del teorema de los cuatro colores en 1852.

El problema del mapa de cuatro colores fue planteado, por primera vez, por el estudiante Francis Guthrie en 1852, lo que fue comunicado a Augustus de Morgan.​ La conjetura se hizo famosa con la declaración de Arthur Cayley, en 1878, en el sentido de que la había abordado. Fue resuelto, a mediados de 1970, por Kenneth Appel y Wolfgang Haken.​

La demostración de Appel-Haken consiste en analizar un gran número de configuraciones reducibles. Esto fue mejorado en 1997 por Robertson, Sanders, Seymour y Thomas, que consiguieron reducir el número de tales configuraciones a 633, lo que sigue siendo un caso de análisis extremadamente largo. En 2005, Georges Gonthier verificó el teorema utilizando un programa informático de demostración de teoremas de uso general.

Formulación precisa del teorema

En primer lugar, todas las esquinas y puntos en común que pertenecen a tres o más países, deben ser ignoradas. Sin esta restricción, los mapas extraños (utilizando las regiones del área finita pero perímetro infinito) pueden requerir más de cuatro colores.

Ejemplo de un mapa de Azerbaiyán con regiones no continuas

En segundo lugar, para el propósito del teorema cada "país" tiene que ser una región simplemente conexa o continua. En el mundo real, esto no es cierto (por ejemplo, Alaska como parte de los Estados Unidos, Nakhchivan como parte de Azerbaiyán, Kaliningrado como parte de Rusia o Llivia como parte de España no son regiones continuas). Debido a que el territorio de un país en particular debe ser del mismo color, si se permitiesen "países" no continuos, cuatro colores podrían no ser suficientes. Por ejemplo, considérese un mapa simplificado:

En este mapa, las dos regiones A pertenecen a un mismo país, y por lo tanto, deben ser del mismo color. En consecuencia, este mapa requiere cinco colores, puesto que las dos regiones A son contiguas con las otras cuatro regiones, y cada una de estas regiones son contiguas entre sí. Si hay tres regiones A, entonces se necesitan seis o más colores; se pueden construir mapas que requieren un número arbitrariamente elevado de colores. Un escenario similar también se puede dar si el color azul se reserva para el agua.

Mapa y grafo dual asociado

Una versión más simple del teorema utiliza la teoría de grafos. El conjunto de las regiones de un mapa se puede representar de manera más abstracta como un grafo simple no dirigido asociando un vértice para cada región y una arista para cada par de regiones que comparten un segmento de borde. Esta representación del mapa con vértices y aristas es un grafo dual y el problema de colorear países se cambia por la coloración del grafo. Este grafo es plano, o sea, que se puede dibujar en el plano sin cruce de aristas mediante la colocación de cada vértice en un lugar elegido arbitrariamente dentro de la región a la que corresponde. Con la terminología de la teoría de grafos, el teorema de cuatro colores establece que:

Teorema de los 4 colores. Si $G\,$ es un grafo plano, entonces $\chi (G)\leq 4$

Es decir, los vértices de cada grafo plano pueden ser coloreados con un máximo de cuatro colores de modo que no existan dos vértices adyacentes con el mismo color. χ(G) corresponde al número cromático.

Historia

El teorema de los cuatro colores surgió como conjetura. En 1852, Francis Guthrie era un estudiante de Augustus De Morgan y formuló esa conjetura, que no pudo ser probada por Guthrie, ni por su hermano Frederick, que había sido también estudiante de De Morgan, ni por sir William Rowan Hamilton, a quien De Morgan le escribió formulando la conjetura.

En 1879 Alfred Bray Kempe anunció en la revista Nature que tenía una demostración para la conjetura. En 1890, Percy John Heawood encontró un error en la demostración de Kempe. Heawood no pudo demostrar que la conjetura no era válida, pero siguió trabajando en el coloreo de mapas, pudiendo probar que con cinco colores se podía colorear cualquier mapa.​

En 1976 la conjetura tuvo demostración, gracias a Kenneth Appel y Wolfgang Haken, que utilizaron un ordenador para la demostración, lo cual generó múltiples controversias en el ambiente matemático.

La polémica demostración

El teorema de cuatro colores fue demostrado con la ayuda de un ordenador. Sin embargo, la demostración no es aceptada por todos los matemáticos dado que sería impracticable por su gran cantidad de detalles, de manera que una persona se vería imposibilitada para verificarlo manualmente. Solo queda aceptar la exactitud del programa, del compilador y del computador en el cual se ejecutó la prueba.

Otro aspecto de la demostración, que puede ser considerado negativo, es su falta de elegancia. Una crítica que habla sobre la elegancia de la misma, comentada en la época de su publicación, dice:

«una buena prueba matemática es similar a un poema —¡pero esto es una guía telefónica!».​

Simplificación y verificación

Desde que se demostró el teorema, un nuevo enfoque ha llevado a una demostración más corta y a un algoritmo más eficiente para los mapas de 4 colores. En 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour y Robin Thomas crearon un algoritmo de tiempo cuadrático (que requiere sólo $O(n^{2})$ de tiempo, donde n es el número de vértices), mejorando un algoritmo de tiempo cuártico basado en la prueba de Appel y Haken​ La nueva prueba, basada en las mismas ideas, es similar a la de Appel y Haken pero más eficiente porque reduce la complejidad del problema y requiere comprobar sólo 633 configuraciones reducibles. Tanto la parte de inevitabilidad como la de reducibilidad de esta nueva prueba deben ser ejecutadas por un ordenador y no es práctico comprobarlas a mano.​ En 2001, los mismos autores anunciaron una prueba alternativa, demostrando la conjetura de la teoría de grafos snark.​ Sin embargo, esta prueba sigue sin publicarse.

En 2005, Benjamin Werner y Georges Gonthier formalizaron una prueba del teorema dentro del asistente de pruebas Coq. Esto eliminó la necesidad de confiar en los diversos programas informáticos utilizados para verificar casos particulares; sólo es necesario confiar en el núcleo de Coq.​

Resumen de las ideas de la demostración

El siguiente resumen está basado en el libro Every Planar Map is Four Colorable de Appel y Haken publicado en 1989. Aunque la prueba del teorema de los cuatro colores dada por Kempe contenía un fallo, proporcionó algunas de las herramientas básicas utilizadas posteriormente para demostrarlo. La explicación que se da aquí se ha reformulado utilizando términos modernos de la teoría de grafos.

El argumento de Kempe es el siguiente. En primer lugar, si el grafo tiene regiones o caras planas no triangulares, es decir, no tienen tres aristas como fronteras, se pueden agregar aristas al grafo (sin introducir nuevos vértices) de manera que cada región del grafo sea triangular, incluida la región exterior. Si este grafo triangular obtenido del original admite una coloración con cuatro colores o menos, entonces el grafo inicial también admite la misma coloración (o una coloración con menos colores), ya que la coloración sigue siendo válida si se eliminan las aristas introducidas. Así que basta demostrar el teorema de los cuatro colores para el caso particular de los grafos triangulares para probarlo a todos los grafos planos, y sin pérdida de generalidad, suponemos que el grafo es triangular.

Supongamos que v, a, y c es el número de vértices, aristas y regiones. Dado que cada región es triangular y cada arista es compartida por dos regiones, tenemos que 2a = 3c. Esto, junto con la fórmula del teorema de Euler para poliedros (v - a + c = 2) se puede utilizar para demostrar que 6v - 2a = 12. Ahora bien, el grado de un vértice es el número de las aristas incidentes. Si v_n es el número de vértices de grado n, y D es el grado máximo de un vértice, se tiene:

$6v-2a=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$

Pero 12 > 0, es un número positivo y "6 - i ≤ 0" para todo "i ≥ 6", esto demuestra que existe al menos un vértice de grado 5 o menos.

Si existe un grafo que requiere 5 colores, entonces existe un grafo minimal, donde la eliminación de cualquier vértice lo hace cuatro colorable. Llamemos a este grafo G. El grafo G no puede tener un vértice de grado 3 o menos, porque si g(v) ≤ 3, podemos eliminar v de G, y colorear con cuatro colores el grafo modificado más pequeño, y a continuación, añadir de nuevo el vértice v y colorearlo con un color diferente al de sus vecinos.

Kempe también demostró que G no puede tener ningún vértice de grado 4. Como antes se elimina el vértice v, y cuatro colores de los vértices restantes. Si los cuatro vecinos de v son de diferentes colores, por ejemplo rojo, verde, azul y amarillo en sentido horario, buscamos una ruta alterna de vértices de color rojo y azul que una los vecinos rojo y azul. Tal camino se llama una cadena de Kempe. Puede haber una cadena de Kempe uniendo a los vecinos de color rojo y azul, y puede haber una cadena de Kempe uniendo a los vecinos verdes y amarillos, pero no ambos, ya que estos dos caminos necesariamente se cruzan, y el vértice donde se interceptan no puede ser coloreado. Supongamos que se trata a los vecinos rojas y azules que no están encadenados entre sí. Explora todos los vértices conectados al vecino rojo por el rojo-azul caminos alternos, y luego invertir los colores rojo y azul en todos estos vértices. El resultado sigue siendo un válido de cuatro colores, y ahora v se puede agregar de nuevo y de color rojo.

Esto deja solo el caso en que G tiene un vértice de grado 5; pero el argumento de Kempe era defectuoso para este caso particular. Heawood notó el error de Kempe y también advirtió que si se estaba satisfecho con probar que solo cinco colores son necesarios, se podría usar el argumento anterior (cambiando el contraejemplo por uno que requiere 6 colores) y usar las cadenas de Kempe en el vértice de grado 5 para demostrar el teorema de los cinco colores:

Teorema de los cinco colores. Si $G\,$ es un grafo plano, entonces $\chi (G)\leq 5$ Heawood (1890)

Generalizaciones

Uniendo las flechas simples y las flechas dobles, se obtiene un toro con siete regiones colindantes, con lo que son necesarios siete colores.

Esta construcción muestra un toro dividido en el máximo de siete regiones, cada una de las cuales toca a las otras.

Se ha estudiado también el problema de colorear otras superficies que no sean equivalentes a un plano. Para superficies cerradas (orientables o no orientables) con género positivo, el número máximo de colores p que se necesitan depende de la característica de Euler χ, dados por la siguiente fórmula:

$p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,$

donde los paréntesis externos determinan la función parte entera.

Alternativamente, para una superficie orientable, la fórmula puede ser dada en términos del género de la superficie, g:

$p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor$ (Weisstein).

Esta fórmula, conocida como conjetura de Heawood, fue conjeturada por P. J. Heawood en 1890 y demostrada para los casos de superficies orientables (y no orientables) no acotadas por Gerhard Ringel y J. T. W. Youngs en 1968. La única excepción a la fórmula es la Botella de Klein, que tiene una característica de Euler 0 (de ahí la fórmula da p=7) y requiere 6 colores, como lo demostró P. Franklin en 1934 (Weisstein). (Una Banda de Möbius, cuya característica de Euler χ = 0, también requiere 6 colores, pero en este caso la fórmula no es aplicable, puesto que es una superficie acotada. (Weisstein))

El toro tiene una característica de Euler χ = 0 (y género g = 1) y por lo tanto p = 7, de manera que no más de 7 colores son requeridos para colorear cualquier mapa sobre un toro. El Poliedro de Szilassi es otro ejemplo que requiere 7 colores.

No hay extensión obvia del problema de coloreo de regiones de sólidos tridimensionales. Usando un conjunto de n varillas flexibles, uno puede hacer que cada varilla toque a cada una de las otras. El conjunto luego requerirá n colores, o n+1 si se considera que el espacio vacío también toca cada varilla. Para el número n puede tomarse un entero tan grande como se quiera. tales ejemplos fueron propuestos por Fredrick Gurthrie en 1880.(Wilson, 2002)

Falsas refutaciones

El teorema de los cuatro colores ha sido famoso por atraer un gran número de pruebas y refutaciones falsas en su larga historia. Al principio, The New York Times se negó, por política, a informar sobre la prueba de Appel-Haken, temiendo que la prueba se mostrara falsa como las anteriores.​ Algunas supuestas pruebas, como las mencionadas de Kempe y Tait, estuvieron bajo el escrutinio público durante más de una década antes de ser refutadas. Pero muchas otras, de autoría de aficionados, nunca llegaron a publicarse.

En el primer mapa, que excede de cuatro colores, la sustitución de las regiones rojas con cualquiera de los otros cuatro colores no funcionaría, y el ejemplo puede parecer inicialmente violar el teorema. Sin embargo, los colores pueden reordenarse, como se ve en el segundo mapa.

Generalmente, los contraejemplos más sencillos, aunque no válidos, intentan crear una región que toque a todas las demás regiones. 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 se centra en la región grande, no se da cuenta de que las regiones restantes pueden colorearse con tres colores.

Este truco puede generalizarse: hay muchos mapas en los que, si se seleccionan de antemano los colores de algunas regiones, resulta imposible colorear las restantes sin sobrepasar los cuatro colores. Un verificador casual del contraejemplo puede no pensar en cambiar los colores de estas regiones, de modo que el contraejemplo aparecerá como válido.

Tal vez un efecto subyacente 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 de color diferente de las regiones que toca directamente, no las regiones que tocan las regiones que toca. Si ésta fuera la restricción, los grafos planos requerirían un número arbitrariamente grande de colores.

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

Referencias

Mapa de los estados de Estados Unidos en formato de cuatro colores.

Bibliografía

mapa de los departamentos de Francia en cuatro colores.

• Gonthier, Georges (2008), «Formal Proof--The Four-Color Theorem», Notices of the American Mathematical Society 55 (11): 1382-1393 . (en inglés)
• Wilson, Robin (2002), Four Colors Suffice, London: Penguin Books, ISBN 0-691-11533-8 .
• Weisstein, Eric W. «Four-Color Theorem». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.  (en inglés)
• Weisstein, Eric W. «Map coloring». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.  (en inglés)

• Howard Levi, An algebraic reformulation of the four color theorem Archivado el 4 de marzo de 2016 en Wayback Machine. (en inglés), publicado atítulo póstumo por Don Coppersmith, Melvin Fitting y Paul Meyer.

Véase también

• Coloración de grafos
• Grafos sin triángulos
• Snark (teoría de grafos)

Enlaces externos

Mapa de los oblasts de Ucrania en formato cuatro colores.

• Wikimedia Commons alberga una categoría multimedia sobre Teorema de los cuatro colores.
• Teorema de los cuatro colores Artículo divulgativo sobre la historia del problema de los cuatro colores.

• Datos: Q184410
• Multimedia: Four-color theorem / Q184410