El problema de los cinco colores

Uno de los problemas más bonitos con los que me he podido topar a lo largo de la carrera es sin duda el, desde hace ya unos 40 años conocido como, teorema de los cuatro colores.

Este teorema afirma que cualquier mapa puede colorearse con, a lo sumo, cuatro colores.

…y con uno si quieres.

 Cierto, se me olvida la condición: dos regiones adyacentes no pueden tener el mismo color.

…sigue sin parecer muy difícil.

Cierto, su formulación es engañosa. Algo parecido pasa con el teorema de la curva de Jordan (una curva cerrada, y sin autointersecciones, separa el plano en dos: la región de dentro y la región de fuera). Ambos resultados pueden enunciarse de una manera insultantemente simple y  tienen una dificultad para su demostración no comparable a su sencilla formulación.

Un dato: la demostración del problema o conjetura de los cuatro colores, formulada originalmente por el botánico y matemático Francis Guthrie en el año 1852, fue probada por medios no convencionales en 1976 por los matemáticos Kenneth Appel y Wolfgang Haken.

 No convencionales = Usando ordenadores 

 No nos confundamos. No se pusieron a colorear mapa por mapa, o mejor dicho grafo por grafo, todos los imaginables. Aunque si colorearon unos 2000 grafos que representaban a todos ellos.

Un fragmento tomado de Every planar map is four colorable, el artículo de Appel y Haken. Solo con la imágen se intuye cierta fuerza bruta en la demostración.

Aún con todo, esta demostración supuso un gran alboroto en el mundillo matemático, y la longitud de la misma no ayudaba a su aceptación. Alguien de aquel entonces llegó a decir

A good mathematical proof is like a poem. This is a telephone directory!

 Lo sé, lo sé. Llevo ya un rato hablando del teorema de los cuatro colores. Pero, entonces…

¿a qué viene el cinco de la entrada?

 A que vamos a demostrar en unas pocas líneas el teorema de los cinco colores.

Sí, eso es. Aunque parezca de chiste: un lapicero más, un marrón, y todo se vuelve simple.

La prueba que exponemos ahora es la que se presenta en Another Proof of Five Color Theorem de Jin Akiyama y Takashi Hamada.

Teorema. Todo grafo plano es 5-coloreable.

Demostración. Aplicaremos el método de inducción. Es decir, demostraremos p+1 supuesto p.

Primero, esta claro que cualquier grafo con p\leq 5 vértices es 5-coloreable. Basta colorear cada vértice o país del mapa de un color distinto.

Siguiendo con la inducción, asumamos que todo grafo de p vértices es 5-coloreable.

¿Qué puede decirse de un grafo G con p+1 vértices?

Sabemos que todo grafo plano, todo mapa, con al menos cuatro vértices tiene al menos cuatro vértices de grado no mayor que cinco. Esto es, existen cuatro países con no más de cinco países fronterizos.

Si alguno de esos cuatro vértices, v, tiene grado tres o cuatro, entonces G es 5-coloreable.

Esta última afirmación tiene su explicación: si quitamos el vértice v de G, y sus respectivas aristas, obtenemos un grafo G' con p vértices, que por hipótesis de inducción, es 5-coloreable.

Ahora lo coloreamos.

Una vez pintado regresamos el vértice eliminado a su posición original, con sus aristas. En el peor de los casos, los tres o cuatro vértices adyacentes tendrán colores distintos. Pero siempre nos quedará uno.

Por tanto, podemos asumir que todos los vértices del grafo tienen como mínimo cinco vértices fronterizos.

Tomemos un vértice de grado cinco, v, y al igual que antes consideremos

 \displaystyle G' = G - v

Este vértice tenía asociado cinco más, que podemos numerar como v_1,v_2,v_3,v_4 y v_5. Ahora, en G', tomamos dos vértices no adyacentes y los identificamos, es decir, los superponemos. Pongamos que son v_1 y v_4, como en la imagen siguiente.

Ahora estamos en la misma situación de antes. Tras la identificación tenemos un grafo G' de p vértices, y por tanto, por muy mal que parezcan pintar las cosas, es posible pintarlo con cinco colores, por hipótesis de inducción.

Una vez pintado, desidentificamos. Ahora tenemos los cinco vértices coloreados con, como mucho cuatro colores. El vértice v_5 podría tener el mismo color que v_2 o v_3 o bien ser distinto a ellos, y por supuesto a v_1 y v_4.

Sobra un color. Sobra el marrón.

Añadimos de nuevo el vértice v al grafo G', obteniendo de nuevo G. Y coloreamos v con el color marrón.                                                                                          \square

¡Con esto hemos demostrado el teorema de los cinco colores! No son cuatro, pero oye…¡no está nada mal! Aunque, aunque…veo por ahí alguna afirmación, en la demostración, muy dicha a la ligera…nah, será cosa mía. O puede que alguna entrada posterior haya que dedicársela a esa afirmación.

La primera demostración del teorema de los cinco colores se debe a Percy John Heawood en 1890.

Casualidades de la vida: Heawood echó por tierra la demostración de Alfred Kempe del teorema de los cuatro colores, con fecha 1879.

Pero esta demostración no cayó en el olvido. Heawood tomó ideas de la demostración de Kempe y consiguió demostrar una versión débil del teorema de los cuatro colores: el teorema de los cinco colores.

Anuncios
Esta entrada fue publicada en Uncategorized y etiquetada , , , , , , , , , , , , , . Guarda el enlace permanente.

One Response to El problema de los cinco colores

  1. Cool! Esta demostración que proponés es mucho más sencilla de la que me dieron. Thanks!
    Ah! Y no sabía nada de que en realidad son 4-coloreables. (Probablemente lo dijeron en clases y jamás presté atención, jeje).
    Saludos!

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s