.Problema de Gincana: Colorindo mapa

Problema

Qual é a menor quantidade de cores que permite colorir esse mapa, sendo que países com uma fronteira comum não podem ter a mesma cor?

Solução

Considere as regiões denotadas por A, B, C, D e E, como abaixo.

• Claramente não conseguimos colorir o mapa com apenas uma cor, pois países com uma fronteira comum não podem ter a mesma cor.
• Vamos, então, tentar utilizar apenas duas cores para colorir o mapa. Neste caso, a região A é colorida com uma cor, digamos, amarelo, enquanto E recebe outra cor, digamos, rosa. Como D é adjacente a E, D não pode ser colorida de rosa. Tentando usar apenas duas cores, colorimos D de amarelo. Raciocinando de maneira análoga, colorimos C de rosa.
  Porém, chegamos a um impasse: B é adjacente a A, e não pode ser pintada de amarelo. Da mesma forma, B é adjacente a C, não podendo ser rosa.
  
• Então, precisamos de uma terceira cor; digamos, azul.
  

Assim, a menor quantidade de cores para colorir o mapa nas condições enunciadas é 3.

Solução elaborada pelos Moderadores do Blog.