Teorema de los Cuatro Colores

Teoría

El Teorema de los Cuatro Colores es un resultado histórico en la teoría de gráficas y combinatoria que dice que, si tienes cualquier división de un plano en regiones contiguas (un mapa), no necesitas más de cuatro colores para colorear las regiones de tal forma que no haya dos regiones adyacentes que compartan el mismo color. En el lenguaje de teoría de gráficas, esto equivale a decir que toda gráfica plana tiene un número cromático menor o igual a 4. Una gráfica plana es una gráfica que puedes dibujar de tal forma que no haya dos aristas que se crucen. Las regiones del mapa corresponden a los vértices de la gráfica, y las fronteras entre regiones corresponden a las aristas que conectan esos vértices.

Este teorema es importante no solo por su resultado, sino por su historia y su método de demostración. La conjetura apareció en 1852 y nadie pudo demostrarla por más de un siglo. Finalmente, Kenneth Appel y Wolfgang Haken la demostraron en 1976, marcando el primer teorema matemático importante que demostraron con la ayuda de una computadora. La demostración se basa en dos conceptos principales: "conjuntos inevitables" (un conjunto de configuraciones donde al menos una tiene que aparecer en cualquier gráfica plana) y "descarga" (una técnica que usa la fórmula de Euler para distribuir carga entre vértices o caras para demostrar propiedades estructurales).

En las olimpiadas de matemáticas, aunque la demostración completa asistida por computadora