TEOREMA DE LOS CUATRO COLORES

En 1852, Francis Guthrie plantea la siguiente conjetura: "En un plano no se necesitan más de cuatro colores para colorear un mapa de manera que dos regiones vecinas, es decir, que compartan una frontera y no únicamente un punto, no queden coloreadas del mismo color"

Este teorema tiene estrecha relación con la teoría de grafos.

Si los paises están distribuidos como se muestra en la imagen, bastaría sólo con dos colores.

Si se elige un punto para representar a cada país y se traza una línea uniendo dos puntos cada vez que correspondan a dos países adyacentes, se obtiene un grafo como el siguiente.

El problema del coloreado consiste en atribuir un color a cada vértice del grafo, de manera que dos vértices conectados tengan siempre un color diferente. Al distribuir los paises de la siguiente forma, ocuparemos sólo tres colores y obtenemos el siguiente grafo:

En el siguiente caso, necesitamos de 4 colores:

Este grafo es un K4 (completo de 4 vértices), que lo veremos más adelante

En 1976, K. Appel y W. Haken dan una prueba del teorema de los cuatro colores, demostrando mediante un programa computacional que, efectivamente, cuatro colores son suficientes para colorear cualquier mapa plano.

En 1996, N. Robertson, D. P. Sanders, P. Seymour y R. Thomas, publican una nueva prueba, sin los inconvenientes de la demostración de Appel y Haken, como el elevado número de configuraciones a estudiar y el tiempo que todo este procedimiento requiere.

Los grafos no sólo son importantes para los matemáticos. Se usan también para representar
circuitos electricos, además se pueden utilizar para determinar el trayecto óptimo (el menos costoso, el más rápido) de camiones que deben repartir y recoger productos a numerosos clientes, la red de carreteras puede modelizarse por un grafo, cuyas aristas son las carreteras de una ciudad a otra, a cada arista se le asocian varios números: longitud del camino correspondiente, tiempo de recorrido, peajes, etc. A través de grafo se pueden representar las lineas del metro, entre tantas otras aplicaciones.