Aquí dejo la que sería la demostración elegante y formal del teorema de los cuatro colores. Había una «demostración» anterior, llevada a cabo en 1976 por Kenneth Appel y Wolfgang Haken pero no era una demostración como tal, sino un mero proceso de fuera bruta llevado a cabo con 1476 mapas.

DEMOSTRACIÓN FORMAL DEL TEOREMA DE LOS CUATRO COLORES

• El número cromático de un grafo es mayor o igual a 5 si y sólo si contiene, al menos, un subgrafo K5 ó cualquier subdivisión elemental suya.
• Según el teorema de Kuratowski un grafo es planar si y sólo si no contiene ningún subgrafo K5, K3,3 ó cualquier subdivisión elemental de ellos.
• El grafo coloreado que representa un mapa siempre es planar, por lo tanto no contendrá ningún subgrafo K5 ni ninguna subdivisión elemental suya, con lo que su número cromático será, a lo sumo, 4.

PROYECCIÓN BIDIMENSIONAL DE POLIEDROS

• Llamamos proyección bidimensional de un poliedro al resultado de asignar a cada cara un vértice y a cada unión entre dos caras una arista.
• Ningún grafo no planar es la proyección de un poliedro.
• Se puede deducir por tanto que la clique máxima del grafo coloreado que representa un mapa es de orden 4, al ser el grafo K4 el mayor grafo Kn planar.
• Si se razona en tres dimensiones esto es fácil de comprobar: el K4 corresponde a la proyección bidimensional de un tetraedro, y éste es el único poliedro en el que cada una de sus caras está en contacto con todas las demás. El K5 no es planar puesto que no existe ningún poliedro de 5 caras en el que cada una de ellas esté en contacto con todas las demás.

Generalización:

• Si ampliamos la definición de grafo Kn al ámbito de poliedros, podemos decir que el tetraedro es el único poliedro Kn. En cada dimensión, la recta/polígono/poliedro más sencillo siempre es una recta/polígono/poliedro Kn y, además, es el único Kn en su dimensión.
• Así, por ejemplo, en una dimensión la única recta Kn es una recta que une dos puntos, es decir: un segmento. Una recta con 3 o más puntos no es una recta Kn.
• En dos dimensiones el único polígono Kn es el triángulo. Y atención aquí que estamos hablando de polígonos y no de grafos.
• Finalmente, en tres dimensiones el único poliedro Kn es el tetraedro.

CONCLUSIÓN:

• Si aplicamos el coloreo a las figuras de cada dimensión (rectas/polígonos/poliedros) tendremos que el mayor número necesario de colores para dibujar cualquier figura de esa dimensión de modo que no haya dos puntos o caras adyacentes con el mismo color, siempre será igual al número de dimensiones en las que se encuentre dicha figura más uno.
• Cuando hablamos de mapas estamos hablando también de proyección bidimensional de poliedros, y como el mayor número necesario de colores para dibujar un poliedro es 4, también lo será para dibujar un mapa.