Coloración de gráficas planas

El famoso Teorema de los cuatro colores, que logró demostrarse a finales del siglo XX, consiste en probar que bastan cuatro colores para colorear un mapa de forma tal que dos regiones adyacentes nunca tengan el mismo color. Colorear mapas es totalmente equivalente a colorear gráficas planas.