Brincando de colorir mapas

Quantas cores são necessárias para colorir um mapa de modo que as regiões adjacentes não fiquem iguais?

O matemático sul-africano Francis Guthrie estava ‘brincando’ de colorir o mapa da Inglaterra quando percebeu que quatro cores bastavam para realizar a tarefa.        

O problema é fácil de explicar: quantas cores são necessárias para colorir um mapa no plano de forma que as regiões adjacentes – que fazem fronteira entre si – tenham cores diferentes?

Mas há muitas situações em que menos de quatro cores bastam – e não precisamos daquelas mais de mil páginas para entender o porquê! Vejamos, por exemplo, ‘problema das duas cores’.
Considere um mapa – sim, para os matemáticos é um mapa! – formado pela interseção de vários círculos (figura abaixo).

Para mapas assim, duas cores bastam. Se você começar a colorir o mapa, usando azul e vermelho, por exemplo, verá que, feita a escolha da cor para uma região, o processo fica muito natural. Experimente.
Mas a questão, agora, é: como provar que esse método funciona sempre?
 Por que duas regiões fronteiriças não acabam com a mesma cor?

Desafio

E se o mapa fosse formado por quadrados, em vez de círculos, o argumento do ‘problema das duas cores’ ainda valeria?
Veja mais aqui.