Dado un mapa de México, ¿cuántos colores son necesarios para pintar los estados de tal manera que cualesquiera dos que comparten frontera tienen colores diferentes?  Esta pregunta parece ser parte de una tarea tediosa que se puede dar a niños de primaria, pero la pregunta resulta adquiere un aire de mayor seriedad cuándo se pide para cualquier mapa, es decir “¿Cuál es el menor número posible tal que  cualquier mapa se puede colorear con esa cantidad de colores de tal manera que dos secciones que comparten frontera reciben colores diferentes?  Con compartir frontera nos referimos a compartir una parte de curva y no sólo un punto (si no, dividir un disco en secciones angulares muy pequeñas necesitaría muchísimos colores).  Este problema resulta ser uno de los más famosos, no sólo por su aparente simplicidad y su molesta dificultad, sino por la gran controversia que ha causado entre matemáticos.

            El problema se atribuye a Francis Guthrie en 1852, quién intentaba colorear un mapa de Inglaterra con estas reglas y notó que sólo necesitaba 4 colores.  Le comentó a su hermano que era estudiante de Augustus de Morgan (sí, el de las leyes de “de Morgan” en lógica) en quién fue el que hizo que la pregunta se volviera famosa.  A partir de entonces hubo varios intentos de demostración, algunos en los que no se encontró errores por más de 10 años, pero al final de cuentas todas con fallas.  Cabe notar que demostrar que con 5 colores se puede colorear cualquier mapa es algo relativamente sencillo, y es parte de casi cualquier buen primer curso de teoría de gráficas (“ya que cualquier gráfica plana tiene número cromático menor o igual a 5” diría una persona familiar con el tema).  Sin embargo, ver que cualquier mapa se puede colorear con 4 colores (o encontrar un mapa que necesite 5) fue un problema que se mantuvo sin resolver por más de 100 años.

            El problema fue resuelto en 1976, demostrando que para cualquier mapa 4 colores son suficientes.  La demostración consitió en reducir el problema a 1936 casos y luego ver que estos cumplían la propiedad.  Sin embargo, al hacer esto necesitaron hacer uso de supercomputadoras, ya que al hacerlo mano necesitarían cientos de páginas escritas para terminar la demostración.  Este fue el primer ejemplo de un problema importante que se resolvía usando una computadora.  El mayor problema es que uno tiene que confiar en que la computadora lo hizo bien.  Es decir, hay que confiar que el programa sí da una solución de verdad para el problema.  Esto causo una gran controversia entre matemáticos, ya que realmente no hay manera de checar que la demostración esté bien hecha.  Se han hecho varias reducciones a la demostración para que la parte que tiene que hacer la computadora sea menor y haya menos puntos en los que hay que confiar “ciegamente” en ella, pero estas partes todavía existen.  El problema ya era muy famoso para entonces, pero hubo incluso periódicos que no les interesaba reportar al respecto porque el problema ya había recibido tantas demostraciones falsas que no confiaban en que esta estuviera bien.  Puede sonar un poco exagerado, pero querían evitar algo como lo que pasó con la conjetura P vs NP hace una año con la solución de Vinay Deolalikar (la cual lamentablemente tenía errores).  A pesar de que cada vez ha ganado más aceptación la demostración por computadora, todavía hay matemáticos que consideran que el problema no está resuelto.

            Hay una pregunta muy natural que sigue a este problema.  Aquí, uno no va a hacer un mapa plano, pero un mapa en otro superficie.  Por ejemplo, ¿qué sucede si uno hace un mapa en un cilindro, en un esfera, o en una dona?  Es curioso que en varias superficies el mínimo número de colores sigue siendo 4, como la esfera y el cilindro, pero en otras no.  Por ejemplo, en la figura se muestra un mapa en la superficie de la dona que requiere de 7 colores (y en el caso de la dona, este es el mínimo).  Uno puede incluso tratar con superficies que no caben en un espacio de tres dimensiones, como la botella de klein (para los curiosos, aquí se necesitan 6 y no más).  Otra pregunta interesante es cuándo es que 3 colores son suficientes.  Resulta que si no hay 3 secciones A, B, C tales que cualesquiera dos de ellos tienen fronteras, 3 colores son suficientes.

            Lamentablemente este problema no tiene equivalente en dimensiones más grandes.  Esto es porque se pueden encontrar secciones en el espacio tales que requieren tanto colores como queramos para colorearlos de tal manera que si comparten una parte plana tengan colores diferentes.  Sin embargo, encontrar una demostración del problema original que no use computadoras todavía sería un resultado muy importante.