En matemáticas , el teorema de los cuatro colores , o teorema del mapa de los cuatro colores , establece que no se requieren más de cuatro colores para colorear las regiones de cualquier mapa de modo que no haya dos regiones adyacentes que tengan el mismo color. Adyacente significa que dos regiones comparten un límite común de longitud distinta de cero (es decir, no simplemente una esquina donde se encuentran tres o más regiones). [1] Fue el primer teorema importante que se demostró utilizando una computadora . Inicialmente, esta prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadora era inviable para que un humano la verificara a mano . [2] La prueba ha ganado una amplia aceptación desde entonces, aunque persisten algunas dudas. [3]
El teorema es una versión más fuerte del teorema de los cinco colores , que se puede demostrar utilizando un argumento significativamente más simple. Aunque el teorema de los cinco colores, más débil, ya se demostró en el siglo XIX, el teorema de los cuatro colores resistió hasta 1976, cuando fue demostrado por Kenneth Appel y Wolfgang Haken . Esto se produjo después de muchas pruebas falsas y contraejemplos erróneos en las décadas anteriores.
La prueba de Appel-Haken se realiza analizando un gran número de configuraciones reducibles. En 1997, Robertson, Sanders, Seymour y Thomas mejoraron este método y lograron reducir el número de configuraciones a 633, lo que sigue siendo un análisis de caso extremadamente largo. En 2005, Georges Gonthier verificó el teorema utilizando un software de demostración de teoremas de propósito general .
En términos de teoría de grafos, el teorema establece que para un grafo plano sin bucles , su número cromático es .
La afirmación intuitiva del teorema de los cuatro colores –“dada cualquier separación de un plano en regiones contiguas, las regiones pueden colorearse usando como máximo cuatro colores, de modo que no haya dos regiones adyacentes que tengan el mismo color”– debe interpretarse adecuadamente para que sea correcta.
En primer lugar, las regiones son adyacentes si comparten un segmento límite; dos regiones que comparten solo puntos límite aislados no se consideran adyacentes. (De lo contrario, un mapa en forma de gráfico circular generaría una cantidad arbitrariamente grande de regiones "adyacentes" entre sí en una esquina común y, como resultado, requeriría una cantidad arbitrariamente grande de colores). En segundo lugar, no se permiten regiones extrañas, como aquellas con un área finita pero un perímetro infinitamente largo; los mapas con tales regiones pueden requerir más de cuatro colores. [4] (Para estar seguros, podemos restringir a regiones cuyos límites consisten en un número finito de segmentos de línea recta. Se permite que una región tenga enclaves , es decir, que rodee por completo a una o más regiones). Nótese que la noción de "región contigua" (técnicamente: subconjunto abierto conectado del plano) no es la misma que la de un "país" en mapas regulares, ya que los países no necesitan ser contiguos (pueden tener exclaves ; por ejemplo, la provincia de Cabinda como parte de Angola , Nakhchivan como parte de Azerbaiyán , Kaliningrado como parte de Rusia, Francia con sus territorios de ultramar y Alaska como parte de los Estados Unidos no son contiguos). Si requiriéramos que todo el territorio de un país reciba el mismo color, entonces cuatro colores no siempre son suficientes. Por ejemplo, considere un mapa simplificado:
En este mapa, las dos regiones etiquetadas como A pertenecen al mismo país. Si quisiéramos que esas regiones recibieran el mismo color, entonces se necesitarían cinco colores, ya que las dos regiones A juntas son adyacentes a otras cuatro regiones, cada una de las cuales es adyacente a todas las demás.
Una formulación más simple del teorema utiliza la teoría de grafos . El conjunto de regiones de un mapa se puede representar de forma más abstracta como un grafo no dirigido que tiene un vértice para cada región y una arista para cada par de regiones que comparten un segmento límite. Este grafo es plano : se puede dibujar 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 sin cruces que conducen desde el vértice de una región, a través de un segmento límite compartido, hasta el vértice de una región adyacente. A la inversa, cualquier grafo plano se puede formar a partir de un mapa de esta manera. En la terminología de la teoría de grafos, el teorema de los cuatro colores establece que los vértices de cada grafo plano se pueden colorear con un máximo de cuatro colores de modo que no haya dos vértices adyacentes que reciban el mismo color, o para abreviar: cada grafo plano es de cuatro colores . [5]
Hasta donde se sabe, [6] la conjetura fue propuesta por primera vez el 23 de octubre de 1852, [7] cuando Francis Guthrie , mientras intentaba colorear el mapa de los condados de Inglaterra, se dio cuenta de que solo se necesitaban cuatro colores diferentes. En ese momento, el hermano de Guthrie, Frederick , era estudiante de Augustus De Morgan (el ex asesor de Francis) en el University College de Londres . Francis le preguntó a Frederick al respecto, quien luego se lo llevó a De Morgan (Francis Guthrie se graduó más tarde en 1852, y más tarde se convirtió en profesor de matemáticas en Sudáfrica). Según De Morgan:
Un alumno mío [Guthrie] me pidió hoy que le diera una razón para un hecho que yo no sabía que era un hecho (y que todavía no sé). Dice que si una figura se divide de alguna manera y los compartimentos se colorean de manera diferente, de modo que las figuras con cualquier porción de línea divisoria común tienen colores diferentes (se pueden necesitar cuatro colores, pero no más). El siguiente es su caso en el que se necesitan cuatro colores. ¿No se puede inventar una necesidad de cinco o más colores? [8]
"FG", tal vez uno de los dos Guthrie, publicó la pregunta en The Athenaeum en 1854, [9] y De Morgan volvió a plantearla en la misma revista en 1860. [10] Otra referencia publicada tempranamente por Arthur Cayley (1879) a su vez atribuye la conjetura a De Morgan.
Hubo varios intentos fallidos de demostrar el teorema. De Morgan creía que se deducía de un simple hecho sobre cuatro regiones, aunque no creía que ese hecho pudiera derivarse de hechos más elementales.
Esto se produce de la siguiente manera: nunca necesitamos cuatro colores en un vecindario a menos que haya cuatro condados, cada uno de los cuales tenga límites comunes con cada uno de los otros tres. Tal cosa no puede suceder con cuatro áreas a menos que una o más de ellas estén encerradas por el resto; y el color usado para el condado encerrado queda así libre para continuar. Ahora bien, este principio de que cuatro áreas no pueden tener límites comunes con las otras tres sin un cercado no es, creemos plenamente, susceptible de demostración sobre algo más evidente y más elemental; debe permanecer como un postulado. [10]
Una de las pruebas propuestas fue dada por Alfred Kempe en 1879, que fue ampliamente aclamada; [11] otra fue dada por Peter Guthrie Tait en 1880. No fue hasta 1890 que Percy Heawood demostró que la prueba de Kempe era incorrecta, y en 1891, Julius Petersen demostró que la prueba de Tait era incorrecta —cada prueba falsa permaneció sin ser cuestionada durante 11 años. [12]
En 1890, además de exponer la falla en la prueba de Kempe, Heawood demostró el teorema de los cinco colores y generalizó la conjetura de los cuatro colores a superficies de género arbitrario. [13]
Tait, en 1880, demostró que el teorema de los cuatro colores es equivalente a la afirmación de que un determinado tipo de gráfico (llamado snark en la terminología moderna) debe ser no plano . [14]
En 1943, Hugo Hadwiger formuló la conjetura de Hadwiger , [15] una generalización de largo alcance del problema de los cuatro colores que todavía permanece sin resolver.
Durante los años 1960 y 1970, el matemático alemán Heinrich Heesch desarrolló métodos para utilizar computadoras para buscar una prueba. Cabe destacar que fue el primero en utilizar la descarga para demostrar el teorema, lo que resultó ser importante en la parte de inevitabilidad de la posterior prueba de Appel-Haken. También amplió el concepto de reducibilidad y, junto con Ken Durre, desarrolló una prueba de computadora para ello. Desafortunadamente, en esta coyuntura crítica, no pudo obtener el tiempo de supercomputadora necesario para continuar con su trabajo. [16]
Otros adoptaron sus métodos, incluido su método asistido por ordenador. Mientras otros equipos de matemáticos se apresuraban a completar las pruebas, Kenneth Appel y Wolfgang Haken, de la Universidad de Illinois , anunciaron el 21 de junio de 1976 [17] que habían demostrado el teorema. Contaron con la ayuda de John A. Koch en algunos trabajos algorítmicos. [18]
Si la conjetura de los cuatro colores fuera falsa, habría al menos un mapa con el menor número posible de regiones que requiere cinco colores. La prueba demostró que no puede existir un contraejemplo mínimo de este tipo, mediante el uso de dos conceptos técnicos: [19]
Utilizando reglas y procedimientos matemáticos basados en propiedades de configuraciones reducibles, Appel y Haken encontraron un conjunto inevitable de configuraciones reducibles, probando así que no podía existir un contraejemplo mínimo a la conjetura de los cuatro colores. Su prueba redujo la infinitud de posibles aplicaciones a 1.834 configuraciones reducibles (más tarde reducidas a 1.482) que tuvieron que ser comprobadas una por una por computadora y tomaron más de mil horas. Esta parte de reducibilidad del trabajo fue verificada independientemente con diferentes programas y computadoras. Sin embargo, la parte de inevitabilidad de la prueba fue verificada en más de 400 páginas de microfichas , que tuvieron que ser revisadas a mano con la ayuda de la hija de Haken, Dorothea Blostein . [20]
El anuncio de Appel y Haken fue ampliamente difundido por los medios de comunicación de todo el mundo, [21] y el departamento de matemáticas de la Universidad de Illinois utilizó un matasellos que decía "Cuatro colores son suficientes". [22] Al mismo tiempo, la naturaleza inusual de la prueba (fue el primer teorema importante que se demostró con amplia asistencia informática) y la complejidad de la parte verificable por humanos despertaron una considerable controversia. [23]
A principios de los años 1980, se extendieron rumores de un fallo en la prueba de Appel-Haken. Ulrich Schmidt en RWTH Aachen había examinado la prueba de Appel y Haken para su tesis de maestría que se publicó en 1981. [24] Había revisado alrededor del 40% de la parte de inevitabilidad y encontró un error significativo en el procedimiento de descarga (Appel y Haken 1989). En 1986, el editor de Mathematical Intelligencer le pidió a Appel y Haken que escribieran un artículo que abordara los rumores de fallas en su prueba. Respondieron que los rumores se debían a una "mala interpretación de los resultados [de Schmidt]" y se comprometieron con un artículo detallado. [24] Su obra maestra , Every Planar Map is Four-Colorable , un libro que afirmaba tener una prueba completa y detallada (con un suplemento en microfichas de más de 400 páginas), apareció en 1989; Explicó y corrigió el error descubierto por Schmidt, así como varios otros errores encontrados por otros. [20]
Desde la demostración del teorema, un nuevo enfoque ha llevado a una prueba más corta y a un algoritmo más eficiente para 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 solo tiempo O ( n 2 ), donde n es el número de vértices), mejorando un algoritmo de tiempo cuártico basado en la prueba de Appel y Haken. [25] 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 verificar solo 633 configuraciones reducibles. Tanto la parte de inevitabilidad como la de reducibilidad de esta nueva prueba deben ejecutarse por computadora y son poco prácticas para verificar a mano. [26] En 2001, los mismos autores anunciaron una prueba alternativa, al probar la conjetura de snark . [27] Sin embargo, esta prueba permanece inédita.
En 2005, Benjamin Werner y Georges Gonthier formalizaron una demostración del teorema dentro del asistente de demostración Coq . Esto eliminó la necesidad de confiar en los diversos programas informáticos utilizados para verificar casos particulares; solo es necesario confiar en el núcleo de Coq. [28]
La siguiente discusión es un resumen basado en la introducción de Every Planar Map is Four Colorable (Appel y Haken 1989). Aunque defectuosa, la supuesta prueba original de Kempe del teorema de los cuatro colores proporcionó algunas de las herramientas básicas que se utilizaron posteriormente para demostrarlo. La explicación aquí se reformula en términos de la formulación de la teoría de grafos moderna mencionada anteriormente.
El argumento de Kempe es el siguiente. En primer lugar, si las regiones planas separadas por el grafo no están trianguladas (es decir, no tienen exactamente tres aristas en sus límites), podemos añadir aristas sin introducir nuevos vértices para hacer que cada región sea triangular, incluida la región exterior ilimitada. Si este grafo triangulado se puede colorear con cuatro colores o menos, también lo es el grafo original, ya que la misma coloración es válida si se eliminan las aristas. Por lo tanto, basta con demostrar el teorema de los cuatro colores para grafos triangulados para demostrarlo para todos los grafos planares, y sin pérdida de generalidad asumimos que el grafo está triangulado.
Supongamos que v , e y f son el número de vértices, aristas y regiones (caras). Como cada región es triangular y cada arista es compartida por dos regiones, tenemos que 2 e = 3 f . Esto, junto con la fórmula de Euler , v − e + f = 2, se puede utilizar para demostrar que 6 v − 2 e = 12. Ahora bien, el grado de un vértice es el número de aristas que lo colindan. Si v n es el número de vértices de grado n y D es el grado máximo de cualquier vértice,
Pero como 12 > 0 y 6 − i ≤ 0 para todo i ≥ 6, esto demuestra que hay al menos un vértice de grado 5 o menos.
Si hay un grafo que requiere 5 colores, entonces hay un grafo mínimo de ese tipo, donde al eliminar cualquier vértice se puede colorear con cuatro colores. Llamemos a este grafo G . Entonces G no puede tener un vértice de grado 3 o menor, porque si d ( v ) ≤ 3, podemos eliminar v de G , colorear con cuatro colores el grafo más pequeño, luego agregar de nuevo v y extender la coloración con cuatro colores eligiendo un color diferente de sus vecinos.
Kempe también demostró correctamente que G no puede tener ningún vértice de grado 4. Como antes, eliminamos el vértice v y coloreamos con cuatro colores los vértices restantes. Si los cuatro vecinos de v son de colores diferentes, digamos rojo, verde, azul y amarillo en el orden de las agujas del reloj, buscamos un camino alterno de vértices coloreados en rojo y azul que unan a los vecinos rojo y azul. Tal camino se llama cadena de Kempe . Puede haber una cadena de Kempe que una a los vecinos rojo y azul, y puede haber una cadena de Kempe que una a los vecinos verde y amarillo, pero no ambos, ya que estos dos caminos necesariamente se intersectarían, y el vértice donde se intersecan no puede colorearse. Supongamos que son los vecinos rojo y azul los que no están encadenados. Explore todos los vértices unidos al vecino rojo por caminos alternos rojo-azul, y luego invierta los colores rojo y azul en todos estos vértices. El resultado sigue siendo un cuádruple coloreado válido, y v ahora se puede volver a agregar y colorear de rojo.
Esto deja solo el caso en el que G tiene un vértice de grado 5; pero el argumento de Kempe era defectuoso para este caso. Heawood notó el error de Kempe y también observó que si uno estaba satisfecho con probar que solo se necesitan cinco colores, uno podría ejecutar el argumento anterior (cambiando solo que el contraejemplo mínimo requiere 6 colores) y usar cadenas de Kempe en la situación de grado 5 para probar el teorema de los cinco colores .
En cualquier caso, para tratar este caso de vértice de grado 5 se requiere una noción más complicada que la de eliminar un vértice. En lugar de ello, la forma del argumento se generaliza para considerar configuraciones , que son subgrafos conectados de G con el grado de cada vértice (en G) especificado. Por ejemplo, el caso descrito en la situación de vértice de grado 4 es la configuración que consiste en un único vértice etiquetado como de grado 4 en G . Como antes, basta con demostrar que si se elimina la configuración y el grafo restante se colorea con cuatro colores, entonces la coloración se puede modificar de tal manera que cuando se vuelve a agregar la configuración, la coloración con cuatro colores se puede extender también a ella. Una configuración para la que esto es posible se llama configuración reducible . Si al menos una de un conjunto de configuraciones debe ocurrir en algún lugar de G, ese conjunto se llama inevitable . El argumento anterior comenzó dando un conjunto inevitable de cinco configuraciones (un único vértice con grado 1, un único vértice con grado 2, ..., un único vértice con grado 5) y luego procedió a demostrar que las primeras 4 son reducibles; exhibir un conjunto inevitable de configuraciones donde cada configuración en el conjunto es reducible probaría el teorema.
Como G es triangular, se conoce el grado de cada vértice en una configuración y se conocen todos los bordes internos de la configuración, el número de vértices en G adyacentes a una configuración dada es fijo y se unen en un ciclo. Estos vértices forman el anillo de la configuración; una configuración con k vértices en su anillo es una configuración de k anillos, y la configuración junto con su anillo se denomina configuración anillada . Como en los casos simples anteriores, se pueden enumerar todos los cuatro colores distintos del anillo; cualquier coloración que se pueda extender sin modificación a una coloración de la configuración se denomina inicialmente buena . Por ejemplo, la configuración de un solo vértice anterior con 3 o menos vecinos fue inicialmente buena. En general, el grafo circundante debe volver a colorearse sistemáticamente para convertir la coloración del anillo en una buena, como se hizo en el caso anterior donde había 4 vecinos; para una configuración general con un anillo más grande, esto requiere técnicas más complejas. Debido a la gran cantidad de cuatro colores distintos del anillo, este es el paso principal que requiere asistencia informática.
Finalmente, queda por identificar un conjunto inevitable de configuraciones que se puedan reducir mediante este procedimiento. El método principal utilizado para descubrir dicho conjunto es el método de descarga . La idea intuitiva que subyace a la descarga es considerar el grafo plano como una red eléctrica. Inicialmente, la "carga eléctrica" positiva y negativa se distribuye entre los vértices de modo que el total es positivo.
Recuerde la fórmula anterior:
A cada vértice se le asigna una carga inicial de 6 grados ( v ). Luego, se "hace fluir" la carga redistribuyéndola sistemáticamente desde un vértice a sus vértices vecinos de acuerdo con un conjunto de reglas, el procedimiento de descarga . Como la carga se conserva, algunos vértices aún tienen carga positiva. Las reglas restringen las posibilidades de configuraciones de vértices con carga positiva, por lo que enumerar todas esas configuraciones posibles da como resultado un conjunto inevitable.
Mientras algún miembro del conjunto inevitable no sea reducible, el procedimiento de descarga se modifica para eliminarlo (al tiempo que se introducen otras configuraciones). El procedimiento de descarga final de Appel y Haken era extremadamente complejo y, junto con una descripción del conjunto de configuraciones inevitables resultante, llenaba un volumen de 400 páginas, pero las configuraciones que generaba podían comprobarse mecánicamente para comprobar que eran reducibles. La verificación del volumen que describe el conjunto de configuraciones inevitables se realizó mediante una revisión por pares durante un período de varios años.
Un detalle técnico que no se analiza aquí pero que es necesario para completar la prueba es la reducibilidad por inmersión .
El teorema de los cuatro colores ha sido conocido por haber suscitado un gran número de pruebas y refutaciones falsas a lo largo de su dilatada historia. Al principio, The New York Times se negó, como política, a informar sobre la prueba de Appel-Haken, por temor a que se demostrara que la prueba era falsa, como las anteriores. [21] Algunas supuestas pruebas, como las de Kempe y Tait mencionadas anteriormente, estuvieron bajo escrutinio público durante más de una década antes de ser refutadas. Pero muchas más, escritas por aficionados, nunca fueron publicadas.
En general, los contraejemplos más simples, aunque no válidos, intentan crear una región que toque a todas las demás regiones. Esto obliga a que las regiones restantes se coloreen con solo 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á concentrada en la región grande, no se da cuenta de que las regiones restantes, de hecho, se pueden colorear con tres colores.
Este truco se puede generalizar: hay muchos mapas en los que, si se seleccionan de antemano los colores de algunas regiones, resulta imposible colorear las regiones restantes sin exceder los cuatro colores. Es posible que a un verificador casual del contraejemplo no se le ocurra cambiar los colores de estas regiones, de modo que el contraejemplo parezca válido.
Tal vez un efecto subyacente a esta idea errónea común es el hecho de que la restricción de color no es transitiva : una región solo tiene que tener un color diferente al de las regiones que toca directamente, no a las regiones que tocan a las regiones que toca. Si esta fuera la restricción, los gráficos planares requerirían una cantidad arbitrariamente grande de colores.
Otras refutaciones falsas violan los supuestos del teorema, como usar una región que consta de múltiples partes desconectadas o no permitir que regiones del mismo color se toquen en un punto.
Si bien cada mapa planar se puede colorear con cuatro colores, es NP-completo en complejidad decidir si un mapa planar arbitrario se puede colorear con solo tres colores. [29]
Un mapa cúbico puede colorearse con solo tres colores si y solo si cada región interior tiene un número par de regiones vecinas. [30] En el ejemplo del mapa de los estados de EE. UU., Missouri ( MO ) sin salida al mar tiene ocho vecinos (un número par): debe tener un color diferente al de todos ellos, pero los vecinos pueden alternar colores, por lo que esta parte del mapa solo necesita tres colores. Sin embargo, Nevada ( NV ) sin salida al mar tiene cinco vecinos (un número impar): uno de los vecinos debe tener un color diferente al de él y a todos los demás, por lo que aquí se necesitan cuatro colores.
El teorema de los cuatro colores se aplica no solo a grafos planos finitos, sino también a grafos infinitos que se pueden dibujar sin cruces en el plano, e incluso de manera más general a grafos infinitos (posiblemente con un número incontable de vértices) para los cuales cada subgrafo finito es plano. Para demostrar esto, se puede combinar una demostración del teorema para grafos planos finitos con el teorema de De Bruijn–Erdős que establece que, si cada subgrafo finito de un grafo infinito es k -coloreable, entonces todo el grafo también es k -coloreable Nash-Williams (1967). Esto también puede verse como una consecuencia inmediata del teorema de compacidad de Kurt Gödel para la lógica de primer orden , simplemente expresando la colorabilidad de un grafo infinito con un conjunto de fórmulas lógicas.
También se puede considerar el problema de coloración en superficies distintas del plano. [31] El problema en la esfera o cilindro es equivalente al del plano. Para superficies cerradas (orientables o no orientables) con género positivo , el número máximo p de colores necesarios depende de la característica de Euler de la superficie χ según la fórmula
donde los corchetes más externos indican la función del piso .
Alternativamente, para una superficie orientable , la fórmula se puede dar en términos del género de una superficie, g :
Esta fórmula, la conjetura de Heawood , fue propuesta por P. J. Heawood en 1890 y, después de las contribuciones de varias personas, demostrada por Gerhard Ringel y J. W. T. Youngs en 1968. La única excepción a la fórmula es la botella de Klein , que tiene una característica de Euler de 0 (por lo tanto, la fórmula da p = 7) pero requiere solo 6 colores, como lo demostró Philip Franklin en 1934.
Por ejemplo, el toro tiene una característica de Euler χ = 0 (y género g = 1) y, por lo tanto, p = 7, por lo que no se requieren más de 7 colores para colorear cualquier mapa en un toro. Este límite superior de 7 es preciso : ciertos poliedros toroidales como el poliedro de Szilassi requieren siete colores.
Una banda de Möbius requiere seis colores (Tietze 1910), al igual que los grafos uniplanares (grafos dibujados con, como máximo, un cruce simple por arista) (Borodin 1984). Si tanto los vértices como las caras de un grafo planar están coloreados, de tal manera que no haya dos vértices, caras o pares vértice-cara adyacentes que tengan el mismo color, entonces nuevamente se necesitan, como máximo, seis colores (Borodin 1984).
Para los grafos cuyos vértices se representan como pares de puntos en dos superficies distintas, con aristas dibujadas como curvas que no se cruzan en una de las dos superficies, el número cromático puede ser al menos 9 y como máximo 12, pero no se conocen límites más precisos; este es el problema Tierra-Luna de Gerhard Ringel . [32]
No existe una extensión obvia del resultado de la coloración a regiones sólidas tridimensionales. Al utilizar un conjunto de n varillas flexibles, se puede disponer que cada varilla toque a todas las demás varillas. El conjunto requeriría entonces n colores, o n +1 incluyendo el espacio vacío que también toca a cada varilla. El número n puede tomarse como cualquier entero, tan grande como se desee. Fredrick Guthrie conocía ejemplos de este tipo en 1880. [33] Incluso para cuboides paralelos al eje (considerados adyacentes cuando dos cuboides comparten un área límite bidimensional), puede ser necesario un número ilimitado de colores. [34]
Dror Bar-Natan dio una declaración sobre las álgebras de Lie y los invariantes de Vassiliev que es equivalente al teorema de los cuatro colores. [35]
A pesar de la motivación de colorear los mapas políticos de los países , el teorema no es de particular interés para los cartógrafos . Según un artículo del historiador de matemáticas Kenneth May , "Los mapas que utilizan solo cuatro colores son raros, y los que lo hacen generalmente requieren solo tres. Los libros sobre cartografía y la historia de la cartografía no mencionan la propiedad de los cuatro colores". [36] El teorema tampoco garantiza el requisito cartográfico habitual de que las regiones no contiguas del mismo país (como el enclave de Alaska y el resto de los Estados Unidos ) se coloreen de manera idéntica.
