Gráficos y RedesThe Four Colour Theorem

Todos estos mapas se pueden colorear con solo cuatro colores diferentes, pero no es difícil imaginar que otros mapas muy complicados puedan necesitar muchos más colores. De hecho, algunos mapas necesitan al menos cuatro colores, siempre que contengan cuatro países, todos conectados entre sí.

Como antes, podemos convertir un mapa con países y fronteras en un gráfico plano: cada país se convierte en un vértice un borde una cara y países que comparten una frontera tienen el mismo color conectado por un borde:

Ahora queremos colorear los vértices de un gráfico, y dos vértices deben tener un color diferente si están conectados por un borde.