Problema Das Quatro Cores
 
 

Quantas cores serão precisas para colorir um mapa?






Serão suficientes quatro cores  para pintar um mapa plano de forma a que dois países vizinhos não partilhem a mesma cor?

Esta questão surgiu em 23 de Outubro de 1852, quando De Morgan, Professor do University College, em Londres recebia de um aluno, Frederick Guthrie, o enunciado do Problema das Quatro Cores. O autor da questão era o irmão do aluno, Francis Guthrie, a quem o problema ocorrera quando coloria um mapa de Inglaterra.

Vejamos alguns exemplos de mapas já coloridos.

Como pode verificar, num dos mapas utilizam-se apenas três cores enquanto no outro recorremos à utilização de quatro cores. Mas será que poderíamos pintá-lo com menos cores? Pode experimentar outras colorações do segundo mapa diferentes da proposta, no entanto deverá reparar que não conseguiu usar menos de quatro cores.
 
 

Tente agora colorir este mapa, de forma a que dois países vizinhos não partilhem a mesma cor. (Note que dois países se dizem vizinhos quando têm uma fronteira com pelo menos uma linha em comum)

RespostaQuantas cores utilizou?

Deste exemplo, podemos concluir que existem mapas nos quais é necessária a utilização de pelo menos quatro cores.
 
 

Voltando agora à primeira questão.

Serão suficientes quatro cores  para pintar qualquer mapa plano, de forma a que dois países vizinhos não partilhem a mesma cor?

Como resposta a este problema, surge o Teorema das Quatro Cores.

Quatro cores são suficientes para pintar qualquer mapa plano. Mas note-se que, ao dizer-se que quatro cores são suficientes para qualquer mapa, isto não significa que sejam necessárias para cada mapa. Isto é, no máximo são precisas quatro cores. Por exemplo, se considerarmos um tabuleiro de xadrez como sendo um mapa, e cada "casa" do tabuleiro representar um país, então a coloração habitual de um tabuleiro de xadrez mostra-nos que, nesse caso, bastam apenas duas cores.

O Teorema das Quatro Cores é um teorema cuja interpretação é acessível a qualquer pessoa, mesmo que não tenha conhecimentos matemáticos. No entanto, a  demonstração encontrada até hoje é bastante delicada. Além de complicada, exige um longo trabalho, sendo necessária a ajuda do computador.

Se considerarmos o mesmo problema, mas permitindo a utilização de mais uma cor, já é possível demonstrar o resultado correspondente com mais facilidade. Teremos o Teorema das Cinco Cores.

Além de mapas planos, poderemos pensar em mapas que estejam desenhados noutras superfícies como por exemplo num Toro ou numa Tira de Möbius.
 
 

Referências:

RADEMACHER, Hans and TOEPLITZ, Otto; The Enjoyment of Mathematics,  Princeton, (1970)

AIGNER, Martin and ZIEGLER, Günter; Proofs from the Book, Springer.

SILVA, Jorge Nuno; Educação e Matemática, Revista da Associação Professores de Matemática, n.º 60, Novembro/Dezembro (2000).
 
 

http://www.cs.unb.ca/~alopez-o/math-faq/mathtext/node27.html

http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html
 


* As páginas sobre o problema das 4 cores são da autoria de Maria João Resende, que preparou uma apresentação sobre este tema enquanto aluna de Matemática da FCUP, no âmbito das actividades desenvolvidas como bolseira da Fundação Gulbenkian.