Teorema de los cuatro colores

Ejemplo de mapa coloreado con cuatro colores.

El teorema de cuatro colores es un teorema sobre el coloreo de grafos, y establece lo siguiente:

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

Dos regiones se dicen adyacentes si comparten un segmento de borde en común, no solamente un punto.

Es fácil ver que no es posible colorear cualquier mapa en estas condiciones con sólo tres colores, y es laborioso pero no complejo demostrar la propiedad con cinco colores.

El problema de los cuatro colores fue planteado por primera vez por Francis Guthrie en 1852 y resuelto en 1976 por Kenneth Appel y Wolfgang Haken con la ayuda de un ordenador.

La primera demostración

El teorema de cuatro colores ha sido demostrado con la ayuda de un ordenador. La prueba sin embargo, no es aceptada por todos los matemáticos dado que sería impracticable por su gran cantidad de detalles que una persona se vería imposibilitada de verificar manualmente. Sólo queda aceptar la exactitud del programa, del compilador y del computador en el cual se ejecutó la prueba.

Otro aspecto de la prueba, que puede ser considerado negativo, es su falta de elegancia. Una crítica sin mucho sentido que habla sobre la elegancia de la prueba, 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!».​

A favor de la certeza de la demostración ha de mencionarse el hecho de que ha sido repetida muchas veces, obteniéndose siempre el mismo resultado positivo. Lo que, en definitiva, resultaría un apoyo inductivo.

Un ejemplo de esta teoría es el hecho de que Africa, como zona geográfica, no puede ser coloreada con 3 colores.

En 1852 Francis Guthrie planteó por primera vez este teorema y fué resuelto en 1976 por Kennet Appel y Wolfan Haken. No obstante el teorema no ha sido aceptado por los matemáticos modernos debido a que es dificil su comprobación manual.

Actualmente el teorema solo se ha hecho valido para mapas que tengan no más de 38 regiones, y retomando el ejemplo de Africa, que tiene mas de 38 regiones, no podría incluso colorearse con 4 colores sin que queden paises adyacentes con el mismo color.