El Teorema de los cuatro colores

... legendario enigma matemático que pasó siglo y medio sin solución... El enunciado más sencillo de este teorema viene a decir que:

Cualquier mapa geográfico puede ser coloreado con cuatro colores diferentes, de forma que no haya regiones adyacentes con el mismo color.

En realidad hay un montón de matizaciones sobre a qué tipos de mapas es aplicable este teorema, pero debe entenderse aplicando el sentido común. Por ejemplo, las regiones que se tocan en un solo punto no se consideran adyacentes. ...

La aplicación del teorema depende también del tipo de superficie sobre la que esté el mapa: una superficie plana finita o infinita o una esfera son equivalentes en este caso, pero si la superficie que se considera es la de un toro serían necesarios siete colores, no cuatro.

... este problema que se considera uno de los más apasionantes de la topología y la teoría de grafos (incluso existe lo que se denomina coloreo de grafos).

Al igual que con el Teorema de Fermat, encontrar la demostración se consideraba muy difícil, pero haber encontrado un contraejemplo (un mapa, por complicado o grande que fuera, que requiriera cinco colores) hubiera demostrado que el teorema era falso. Y eso lo podría haber hecho casi cualquiera.

La historia comienza con el enunciado original del problema en 1852 cuando Augustus de Morgan lo planeó en una carta escrita a un colega, haciendo referencia a que uno de sus estudiantes, Francis Guthrie, se lo había planteado coloreando un mapa de Inglaterra. Desde entonces matemáticos de todo el mundo trataron de encontrar una demostración de que «cuatro colores son suficientes», pero ésta resultaba siempre esquiva. Notables matemáticos consiguieron ciertos avances, pero ninguna prueba definitiva.

No fue hasta 1976 que Kenneth Appel y Wolfgang Haken publicaron la solución: el teorema era correcto y cuatro colores bastaban para cualquier mapa. Sin embargo, esto no acabó con la polémica.

Appel y Hanken utilizaron un programa de ordenador para completar la demostración, reduciendo el problema inicial a un montón de casos más simples, demostrando con gran esfuerzo que todos eran equivalentes. Debían examinar unas 1.936 configuraciones distintas lo cual resultaba lento, pesado y propenso a errores. De modo que, además de las 500 páginas en papel que contenían todos los cálculos y demostraciones previas, programaron un ordenador (recordatorio: año 1976) para comprobarlas una por una. Cuando el ordenador confirmó que en todas se cumplía el teorema, dieron por resuelta la demostración y la publicaron.

Históricamente, era una nueva forma demostrar teoremas.

La mente humana no era suficiente. Se necesitaba ayuda mecánica.

¿Y sí el programa de ordenador contenía errores? ¿Se podría también demostrar que no los contenía? ¿Era esto una demostración cien por cien segura y cierta, como deben serlo todas las demostraciones matemáticas?

La solución se consideró en general válida pero «poco elegante», y se probaron programas similares en otros ordenadores. Naturalmente, un informático podría no opinar lo mismo y considerarla más elegante incluso que una demostración tradicional. Estas cuestiones de fondo han perdurado hasta nuestros días. Se han hecho algunos avances en reducir la prueba a algo más simple. El sistema de asistencia para comprobar pruebas matemáticas Coq confirmó en 2004 la validez del trabajo de Appel y Hanken. (Llegados a este punto, confiar en que la demostración es válida en realidad requiere sólo confiar en que «el sistema Coq es válido», lo cual proporciona un grado de confianza más elevado. En términos informáticos: tener fe en el hardware, el compilador y los programas. (Y es bien sabido que todos esos componentes pueden fallar. El caso más clamoroso: el bug de divisón en los Pentium).

En el año 2000, el matemático indio Ashay Dharwadker publicó una demostración "al estilo tradicional" del teorema, zanjando así la disputa espúrea sobre si el problema estaba o no resuelto

http://www.microsiervos.com/archivo/libros/four-colors-suffice.html

http://es.wikipedia.org/wiki/Teorema_de_los_cuatro_colores