Teorema de los cuatro colores

Ajustar Compartir Imprimir Citar

Declaración en matemáticas

Ejemplo de un mapa de cuatro colores

A cuatro colores de un mapa de los estados de los Estados Unidos (ignorando lagos y océanos).

En matemáticas, el teorema de los cuatro colores, o el teorema del mapa de cuatro colores, establece que no se requieren más de cuatro colores para colorear las regiones de cualquier mapa, de modo que no hay dos regiones adyacentes que tengan el mismo color. Adyacente significa que dos regiones comparten un segmento de curva límite común, no simplemente una esquina donde se encuentran tres o más regiones. Fue el primer teorema importante que se demostró usando una computadora. Inicialmente, esta prueba no fue aceptada por todos los matemáticos porque la prueba asistida por computadora no era factible para que un ser humano la verificara a mano. La prueba ha ganado una amplia aceptación desde entonces, aunque quedan algunos escépticos.

El teorema de los cuatro colores fue probado en 1976 por Kenneth Appel y Wolfgang Haken después de muchas pruebas falsas y contraejemplos (a diferencia del teorema de los cinco colores, probado en el siglo XIX, que establece que cinco colores son suficientes para colorear un mapa). Para disipar cualquier duda restante sobre la prueba de Appel-Haken, Robertson, Sanders, Seymour y Thomas publicaron en 1997 una prueba más simple que utiliza las mismas ideas y aún se basa en computadoras. En 2005, Georges Gonthier también demostró el teorema con un software de prueba de teoremas de propósito general.

Formulación precisa del teorema

En términos gráficos-teoréticos, el teorema declara que para gráfico plano sin bucle $G$ , su número cromático es ${displaystyle chi (G)leq 4}$ .

La declaración intuitiva del teorema de los cuatro colores: "dada cualquier separación de un plano en regiones contiguas, las regiones se pueden colorear utilizando como máximo cuatro colores para que no haya dos regiones adyacentes que tengan el mismo color" – necesita ser interpretado apropiadamente para ser correcto.

Primero, las regiones son adyacentes si comparten un segmento de límite; dos regiones que comparten solo puntos límite aislados no se consideran adyacentes. En segundo lugar, no se permiten regiones extrañas, como las que tienen un área finita pero un perímetro infinitamente largo; los mapas con tales regiones pueden requerir más de cuatro colores. (Para estar seguros, podemos restringirnos a regiones cuyos límites consisten en un número finito de segmentos de línea recta. Se permite que una región rodee por completo una o más regiones). Tenga en cuenta que la noción de "región contigua" (técnicamente: subconjunto abierto conectado del plano) no es lo mismo que el de un "país" en mapas normales, ya que los países no necesitan ser contiguos (por ejemplo, la provincia de Cabinda como parte de Angola, Nakhchivan como parte de Azerbaiyán, Kaliningrado como parte de Rusia y Alaska como parte de los Estados Unidos no son contiguos). Si requerimos 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 requerirí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. Se puede modelar forzar dos regiones separadas para que tengan el mismo color agregando un 'controlador' uniéndose a ellos fuera del avión.

Tal construcción hace que el problema sea equivalente a colorear un mapa en un toro (una superficie de género 1), que requiere hasta 7 colores para un mapa arbitrario. También se aplica una construcción similar si se usa un solo color para múltiples áreas inconexas, como cuerpos de agua en mapas reales, o si hay más países con territorios inconexos. En tales casos, es posible que se requieran más colores con un género creciente de una superficie resultante. (Consulte la sección Generalizaciones a continuación).

Un mapa con cuatro regiones, y el correspondiente gráfico plano con cuatro vértices.

Una declaración más simple del teorema utiliza la teoría de grafos. El conjunto de regiones de un mapa se puede representar de manera más abstracta como un gráfico no dirigido que tiene un vértice para cada región y un borde para cada par de regiones que comparten un segmento límite. Este gráfico 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 los bordes como curvas sin cruces que parten del vértice de una región, a través de un segmento de límite compartido, al vértice de una región adyacente. Por el contrario, cualquier gráfico plano se puede formar a partir de un mapa de esta manera. En terminología de teoría de grafos, el teorema de los cuatro colores establece que los vértices de cada gráfico plano se pueden colorear con un máximo de cuatro colores para que no haya dos vértices adyacentes que reciban el mismo color, o para abreviar:

Cada gráfico plano es cuatro colores.

Historia

Primeros intentos de prueba

Carta de De Morgan a Hamilton, 23 de octubre de 1852

Hasta donde se sabe, la conjetura se propuso por primera vez el 23 de octubre de 1852, cuando Francis Guthrie, mientras intentaba colorear el mapa de los condados de Inglaterra, notó que solo se necesitaban cuatro colores diferentes. En ese momento, el hermano de Guthrie, Frederick, era alumno de Augustus De Morgan (el exasesor de Francis) en el University College London. 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 luego se convirtió en profesor de matemáticas en Sudáfrica). Según De Morgan:

"Un estudiante 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 aún no. Dice que si una figura es alguna de la forma dividida y los compartimentos de colores diferentes para que figuras con cualquier porción de límites comunes línea son de diferentes colores — cuatro colores pueden ser buscados pero no más— el siguiente es su caso en el que cuatro colores son Quería. La consulta no puede inventarse una necesidad para cinco o más..." (Wilson 2014, p. 18)

"F.G.", quizás uno de los dos Guthries, publicó la pregunta en The Athenaeum en 1854, y De Morgan volvió a plantear la pregunta en la misma revista en 1860. Otra referencia temprana publicada por Arthur Cayley (1879) a su vez acredita la conjetura a De Morgan.

Hubo varios intentos fallidos de demostrar el teorema. De Morgan creía que se derivaba de un hecho simple sobre cuatro regiones, aunque no creía que ese hecho pudiera derivarse de hechos más elementales.

Esto surge de la siguiente manera. Nunca necesitamos cuatro colores en un vecindario a menos que haya cuatro condados, cada uno de los cuales tiene líneas fronterizas en común con cada uno de los otros tres. Tal cosa no puede suceder con cuatro áreas a menos que uno o más de ellos sean encerrados por el resto; y el color utilizado para el condado cerrado es así libre de continuar. Ahora este principio, que cuatro áreas no pueden cada una tener un límite común con los otros tres sin encerrar, no es, creemos plenamente, capaz de demostrar sobre cualquier cosa más evidente y más elemental; debe ser un postulado.

Una prueba propuesta fue dada por Alfred Kempe en 1879, que fue ampliamente aclamada; otro fue dado por Peter Guthrie Tait en 1880. No fue sino 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; indiscutible durante 11 años.

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.

Tait, en 1880, demostró que el teorema de los cuatro colores es equivalente a la afirmación de que cierto tipo de gráfico (llamado snark en la terminología moderna) debe ser no plano.

En 1943, Hugo Hadwiger formuló la conjetura de Hadwiger, una generalización de gran alcance del problema de los cuatro colores que aún permanece sin resolver.

Prueba por ordenador

Durante las décadas de 1960 y 1970, el matemático alemán Heinrich Heesch desarrolló métodos de uso de computadoras para buscar una demostración. En particular, fue el primero en utilizar la descarga para probar el teorema, lo que resultó ser importante en la parte inevitable de la prueba posterior de Appel-Haken. También amplió el concepto de reducibilidad y, junto con Ken Durre, desarrolló una prueba informática para ello. Desafortunadamente, en esta coyuntura crítica, no pudo conseguir el tiempo de supercomputadora necesario para continuar con su trabajo.

Otros adoptaron sus métodos, incluido su enfoque asistido por computadora. Mientras otros equipos de matemáticos competían para completar las pruebas, Kenneth Appel y Wolfgang Haken de la Universidad de Illinois anunciaron, el 21 de junio de 1976, que habían probado el teorema. Fueron asistidos en algún trabajo algorítmico por John A. Koch.

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 mostró que tal contraejemplo mínimo no puede existir, mediante el uso de dos conceptos técnicos:

An conjunto inevitable es un conjunto de configuraciones tales que cada mapa que satisface algunas condiciones necesarias para ser una mínima triangulación no-colorable (como tener un grado mínimo 5) debe tener al menos una configuración de este conjunto.
A configuración reducible es un arreglo de países que no pueden ocurrir en un contraejemplo mínimo. Si un mapa contiene una configuración reducible, el mapa se puede reducir a un mapa más pequeño. Este mapa más pequeño tiene la condición de que si se puede colorear con cuatro colores, esto también se aplica al mapa original. Esto implica que si el mapa original no puede ser coloreado con cuatro colores el mapa más pequeño no puede y por lo tanto el mapa original no es mínimo.

Usando reglas y procedimientos matemáticos basados en las propiedades de las configuraciones reducibles, Appel y Haken encontraron un conjunto inevitable de configuraciones reducibles, demostrando así que no podría existir un contraejemplo mínimo a la conjetura de los cuatro colores. Su prueba redujo la infinidad de mapas posibles a 1.834 configuraciones reducibles (luego reducidas a 1.482) que tuvieron que ser revisadas una a una por computadora y tomó más de mil horas. Esta parte de la reducibilidad del trabajo se verificó dos veces de forma independiente con diferentes programas y computadoras. Sin embargo, la parte de inevitabilidad de la prueba se verificó 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 (Appel & Haken 1989).

El anuncio de Appel y Haken fue ampliamente difundido por los medios de comunicación de todo el mundo, y el departamento de matemáticas de la Universidad de Illinois utilizó un matasellos que decía 'Cuatro colores son suficientes'. Al mismo tiempo, la naturaleza inusual de la prueba (fue el primer teorema importante que se demostró con una amplia asistencia informática) y la complejidad de la parte verificable por humanos despertaron una controversia considerable (Wilson 2014).

A principios de la década de 1980, se difundieron rumores sobre una falla 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 (Wilson 2014, 225). Había revisado alrededor del 40% de la porción de inevitabilidad y encontró un error significativo en el procedimiento de descarga (Appel & Haken 1989). En 1986, el editor de Mathematical Intelligencer pidió a Appel y Haken que escribieran un artículo sobre los rumores de fallas en su prueba. Respondieron que los rumores se debían a una "interpretación errónea de los resultados [de Schmidt]". y obligado con un artículo detallado (Wilson 2014, 225–226). Su obra magna, Every Planar Map is Four-Colorable, un libro que reclama una demostración 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 (Appel & Haken 1989).

Simplificación y verificación

Desde la demostración del teorema, se han encontrado algoritmos eficientes para mapas de 4 colores que requieren solo tiempo O(n²), donde n es el número de vértices. En 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour y Robin Thomas crearon un algoritmo de tiempo cuadrático, mejorando un algoritmo de tiempo cuartico basado en la prueba de Appel y Haken. Esta nueva prueba 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 ser ejecutadas por una computadora y no es práctico verificarlas a mano. En 2001, los mismos autores anunciaron una prueba alternativa, demostrando la conjetura de snark. Sin embargo, esta prueba permanece inédita.

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

Resumen de ideas de prueba

La siguiente discusión es un resumen basado en la introducción a Todo mapa plano tiene cuatro colores (Appel & Haken 1989). Aunque defectuosa, la supuesta prueba original de Kempe del teorema de los cuatro colores proporcionó algunas de las herramientas básicas que luego se usaron para demostrarlo. La explicación aquí se reformula en términos de la formulación de la teoría de grafos moderna anterior.

El argumento de Kempe es el siguiente. Primero, si las regiones planas separadas por el gráfico no están trianguladas, es decir, no tienen exactamente tres aristas en sus límites, podemos agregar aristas sin introducir nuevos vértices para hacer que cada región sea triangular, incluida la no acotada. región exterior. Si este gráfico triangulado se puede colorear usando cuatro colores o menos, también lo es el gráfico original, ya que el mismo coloreado es válido si se eliminan los bordes. Por lo tanto, basta probar el teorema de los cuatro colores para gráficos triangulados para probarlo para todos los gráficos planos, y sin pérdida de generalidad asumimos que el gráfico está triangulado.

Supongamos que v, e y f son el número de vértices, aristas y regiones (caras). Dado que cada región es triangular y cada borde es compartido por dos regiones, tenemos que 2e = 3f. Esto, junto con la fórmula de Euler, v − e + f = 2, puede usarse para mostrar que 6v − 2e = 12. Ahora, el grado de un vértice es el número de aristas que colindan con él. Si v_n es el número de vértices de grado n y D es el grado máximo de cualquier vértice,

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

Pero desde 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 gráfico que requiere 5 colores, entonces hay un gráfico mínimo en el que la eliminación de cualquier vértice lo convierte en cuatro colores. Llame a este gráfico G. Entonces G no puede tener un vértice de grado 3 o menor, porque si d(v) ≤ 3, podemos eliminar v de G, cuatricoloree el gráfico más pequeño, luego vuelva a agregar v y amplíe los cuatro colores eligiendo un color diferente de sus vecinos.

Un gráfico que contiene una cadena de Kempe que consiste en vértices azules y rojos alternantes

Kempe también mostró correctamente que G no puede tener un vértice de grado 4. Como antes, eliminamos el vértice v y cuatricoloramos los vértices restantes. Si los cuatro vecinos de v son de diferentes colores, digamos rojo, verde, azul y amarillo en el sentido de las agujas del reloj, buscamos un camino alternativo de vértices de color rojo y azul que unen a los vecinos rojo y azul. Tal camino se llama cadena de Kempe. Puede haber una cadena de Kempe que une a los vecinos rojo y azul, y puede haber una cadena de Kempe que une a los vecinos verde y amarillo, pero no ambos, ya que estos dos caminos necesariamente se cruzarían, y el vértice donde se cruzan no se puede colorear. 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 cuatro colores válido, y v ahora se puede volver a agregar y colorear en rojo.

Esto deja solo el caso donde G tiene un vértice de grado 5; pero el argumento de Kempe fue erróneo para este caso. Heawood notó el error de Kempe y también observó que si uno estaba satisfecho con demostrar 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 el grado 5 situación para demostrar el teorema de los cinco colores.

En cualquier caso, para lidiar con este caso de vértice de grado 5 se requiere una noción más complicada que quitar un vértice. Más bien, 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 consta de un solo vértice etiquetado como de grado 4 en G. Como se indicó anteriormente, basta con demostrar que si se elimina la configuración y el gráfico restante tiene cuatro colores, entonces el coloreado se puede modificar de tal manera que cuando se vuelve a agregar la configuración, los cuatro colores se pueden extender a ella como bien. Una configuración para la que esto es posible se denomina 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 solo vértice con grado 1, un solo vértice con grado 2,..., un solo vértice con grado 5) y luego procedió a mostrar que los primeros 4 son reducibles; exhibir un conjunto inevitable de configuraciones donde cada configuración en el conjunto es reducible demostraría el teorema.

Debido a que 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 determinada configuración es fijo, y se unen en un ciclo. Estos vértices forman el anillo de la configuración; una configuración con vértices k en su anillo es una configuración de anillo k, y la configuración junto con su anillo se denomina configuración en anillo. Como en los casos simples anteriores, uno puede enumerar todos los distintos cuatro colores del anillo; cualquier coloración que pueda extenderse 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 gráfico circundante debe volver a colorearse sistemáticamente para convertir el color del anillo en uno bueno, 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 susceptibles de reducción 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 gráfico plano como una red eléctrica. "carga eléctrica" inicialmente positiva y negativa se distribuye entre los vértices para que el total sea positivo.

Recuerde la fórmula anterior:

sum _{i=1}^{D}(6-i)v_{i}=12.

A cada vértice se le asigna una carga inicial de 6 grados (v). Entonces uno "fluye" la carga mediante la redistribución sistemática de la carga de un vértice a sus vértices vecinos de acuerdo con un conjunto de reglas, el procedimiento de descarga. Como se conserva la carga, 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 las configuraciones posibles da un conjunto inevitable.

Mientras algún miembro del conjunto inevitable no sea reducible, el procedimiento de descarga se modifica para eliminarlo (mientras se introducen otras configuraciones). El procedimiento de descarga final de Appel y Haken fue extremadamente complejo y, junto con una descripción del conjunto de configuración inevitable resultante, llenó un volumen de 400 páginas, pero las configuraciones que generó se pudieron verificar mecánicamente para que fueran reducibles. La verificación del volumen que describe el conjunto de configuración inevitable se realizó mediante revisión por pares durante un período de varios años.

Un detalle técnico que no se analiza aquí pero que se requiere para completar la prueba es la reducibilidad por inmersión.

Falsas refutaciones

El teorema de los cuatro colores ha sido conocido por atraer una gran cantidad de pruebas falsas y refutaciones en su larga historia. Al principio, The New York Times se negó, como cuestión de política, a informar sobre la prueba de Appel-Haken, por temor a que la prueba se mostrara falsa como las anteriores (Wilson 2014). Algunas supuestas pruebas, como las de Kempe y Tait mencionadas anteriormente, estuvieron bajo el escrutinio público durante más de una década antes de ser refutadas. Pero muchos más, escritos por aficionados, nunca se publicaron.

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

Por lo general, los contraejemplos más simples, aunque inválidos, intentan crear una región que toca todas las demás regiones. Esto obliga a que las regiones restantes se coloreen con solo tres colores. Debido a que el teorema de los cuatro colores es cierto, esto siempre es posible; sin embargo, debido a que la persona que dibuja el mapa se enfoca en una región grande, no se da cuenta de que las regiones restantes pueden, de hecho, colorearse con tres colores.

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

Quizás un efecto subyacente a este concepto erróneo común es el hecho de que la restricción de color no es transitiva: una región solo debe tener un color diferente al de las regiones que toca directamente, no las regiones que tocan las regiones que toca. Si esta fuera la restricción, los gráficos planos requerirían un número arbitrariamente grande de colores.

Otras refutación falsa violan las suposiciones del teorema, como usar una región que consta de varias partes desconectadas o prohibir que las regiones del mismo color se toquen en un punto.

Tres colores

Prueba sin palabras que un mapa de Estados Unidos necesita al menos cuatro colores, incluso ignorando el cuadripunto

Si bien cada mapa plano se puede colorear con cuatro colores, es NP-completo en complejidad decidir si un mapa plano arbitrario se puede colorear con solo tres colores.

Un mapa cúbico se puede colorear con solo tres colores si y solo si cada región interior tiene un número par de regiones vecinas. En el ejemplo del mapa de los estados de EE. UU., Missouri sin salida al mar (MO) tiene ocho vecinos (un número par): debe tener un color diferente al de todos ellos, pero los vecinos pueden alternar los colores, por lo que esta parte del el mapa solo necesita tres colores. Sin embargo, Nevada sin salida al mar (NV) tiene cinco vecinos (un número impar): uno de los vecinos debe tener un color diferente al de él y todos los demás, por lo que aquí se necesitan cuatro colores.

Generalizaciones

Gráficos infinitos

Al unir las flechas individuales juntas y las flechas dobles juntas, se obtiene un toro con siete regiones que se tocan mutuamente; por lo tanto, siete colores son necesarios

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

El teorema de los cuatro colores se aplica no solo a los gráficos planos finitos, sino también a los gráficos infinitos que se pueden dibujar sin cruces en el plano, y aún más generalmente a los gráficos infinitos (posiblemente con un número incontable de vértices) para los cuales cada finito el subgrafo es plano. Para probar esto, se puede combinar una prueba del teorema para grafos planares finitos con el teorema de De Bruijn-Erdős que establece que, si cada subgrafo finito de un grafo infinito es k-coloreable, entonces el grafo completo es también k-colorable 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 gráfico infinito con un conjunto de fórmulas lógicas.

Superficies más altas

También se puede considerar el problema de la coloración en superficies distintas al plano. El problema de la esfera o del 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

p=leftlfloor {frac {7+{sqrt {49-24chi }}}{2}}rightrfloor

donde los corchetes más externos indican la función de suelo.

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

{displaystyle p=leftlfloor {frac {7+{sqrt {1+48g}}}{2}}rightrfloor.}

Esta fórmula, la conjetura de Heawood, fue propuesta por P. J. Heawood en 1890 y, después de las contribuciones de varias personas, fue probada 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 la característica de Euler. 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 la característica de Euler χ = 0 (y el género g = 1) y, por lo tanto, p = 7, por lo que no se requieren más de 7 colores para colorea cualquier mapa en un toroide. Este límite superior de 7 es nítido: ciertos poliedros toroidales como el poliedro Szilassi requieren siete colores.

Una tira de Möbius requiere seis colores (Tietze 1910) al igual que los gráficos de 1 plano (gráficos dibujados con un cruce simple como máximo por borde) (Borodin 1984). Si tanto los vértices como las caras de un gráfico plano están coloreados, de tal manera que no haya dos vértices, caras o pares de vértices y caras adyacentes que tengan el mismo color, entonces nuevamente se necesitan como máximo seis colores (Borodin 1984).

Un toro radialmente simétrico de 7 colores – regiones del mismo color envuelven alrededor de las líneas dotadas
Un toro doble de 8 colores (superficie de género-dos) – burbujas denota una combinación única de dos regiones
Una botella de Klein de 6 colores
La subdivisión de Tietze de una franja Möbius en seis regiones mutuamente adyacentes, que requieren seis colores. Los vértices y bordes de la subdivisión forman una incrustación del gráfico de Tietze sobre la tira.
Modelo de poliedro Szilassi interactivo con cada una de 7 caras adyacentes a cada una – en la imagen SVG, mueva el ratón para rotarlo
Prueba sin palabras de que el número de colores necesarios está desbordado en tres o más dimensiones

Regiones sólidas

No hay una extensión obvia del resultado de coloración a las regiones sólidas tridimensionales. Mediante el uso de un conjunto de n varillas flexibles, se puede disponer que cada varilla toque todas las demás varillas. Entonces, el conjunto requeriría n colores, o n+1, incluido el espacio vacío que también toca cada barra. El número n puede tomarse como cualquier número entero, tan grande como se desee. Tales ejemplos fueron conocidos por Fredrick Guthrie en 1880 (Wilson 2014). 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 (Reed & Allwright 2008; Magnant & Martin (2011)).

Relación con otras áreas de las matemáticas

Dror Bar-Natan hizo una declaración sobre las álgebras de Lie y las invariantes de Vassiliev que es equivalente al teorema de los cuatro colores.

Uso fuera de las matemáticas

A pesar de la motivación de colorear mapas políticos de países, el teorema no es de particular interés para los cartógrafos. Según un artículo del historiador de las matemáticas Kenneth May, "los mapas que utilizan solo cuatro colores son raros, y los que lo hacen generalmente requieren solo tres". Los libros de cartografía y de historia de la cartografía no mencionan la propiedad de los cuatro colores. (Wilson 2014, 2). 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 forma idéntica.