Qual o menor número possível de cores para colorir o mapa do Brasil, conforme a figura a seguir?

A regra é que dois estados adjacentes não podem ser coloridos com a mesma cor.

Dois estados são adjacentes se compartilham um lado – se estiverem unidos por um só ponto, não são adjacentes.

Exemplos.

Um mapa como o abaixo precisa de só duas cores.

O mapa abaixo também precisa de duas cores. Note que todos os estados se encontram num único ponto, no meio, só que dividir um único ponto não conta como vizinho – tem que dividir um lado.

Resposta: são necessárias 4 cores para colorir o mapa do Brasil segundo as regras citadas.

O mapa do BR é complexo e cheio de detalhes. Então vamos abstrair um pouco antes.

Um mapa como o abaixo, que tem 4 regiões adjacentes a uma região central, precisa de três cores. Uma cor no meio, e duas cores alternando. Vale o mesmo para mapa similar, com número par de regiões em torno de uma central.

E se for ímpar? Como a abaixo, que tem 5 regiões em torno de uma área?

Aí não consigo alternar duas cores, e vou precisar de 4: uma no meio, e três cores nas regiões periféricas. Tente para se convencer. O mesmo vale para outros números ímpares de regiões periféricas.

O mapa do BR tem um subgrafo como o último acima, que precisa de 4 cores. É na região de Goiás:

Eu diria para desprezar o DF, que não liga com ninguém e só atrapalha a visualização, e notar que GO está no meio de MT, TO, BA, MG e MS. Cada um desses estados conecta outros, sendo igualzinho ao esquema mostrado anteriormente, que precisa de 4 cores.

Há algum mapa que necessite de mais de 4 cores? Não. Esta é uma resposta famosa, e é o Teorema das Quatro Cores. Inclusive, causou bastante debate à época, porque foi feita uma análise exaustiva por computadores, para provar todos os casos possíveis. Algo meio técnica, meio força bruta. Fato é que precisamos de apenas 4 lápis de cores diferentes para colorir, segundo as regras permitidas, qualquer mapa do mundo!

Vide

Clique para acessar o cnmac_brasil_cromatico_691.pdf

Livro sobre a história do Teorema das Quatro Cores.

Link da Amazon: https://amzn.to/3te4sTb

Desafio: colorir o mapa do Brasil