Teorema das quatro cores

No mapa-múndi pendurado na parede de uma sala de aula, as fronteiras parecem quietas. Mas basta pegar lápis de cor para que surja um enigma que atravessou mais de um século: quantas cores são necessárias para pintar um mapa de modo que regiões vizinhas nunca compartilhem a mesma cor? A resposta — quatro — hoje é um teorema. O caminho até ele, porém, redesenhou o que conta como prova em matemática.

A história começa em 1852 com Francis Guthrie, estudante do University College London. Ao tentar colorir um mapa da Inglaterra, percebeu que quatro cores pareciam sempre bastar. Intrigado, pediu ao irmão Frederick que levasse a questão ao professor Augustus De Morgan. No mesmo dia, De Morgan escreveu a William Rowan Hamilton, em Dublin, descrevendo o problema com ironia e curiosidade: não sabia se era fato, mas suspeitava que quatro cores bastavam — e perguntava se alguém conseguiria forçar a necessidade de cinco. Hamilton respondeu poucos dias depois, sem se comprometer a atacar o “quaternion das cores”.

Guthrie seguiu carreira jurídica e depois foi para a África do Sul como professor de matemática; publicou pouco, interessou-se por botânica e deu nome a uma espécie de urze. O problema que deixara, no entanto, ganhou vida própria. De Morgan o divulgou, e matemáticos na Europa e nos Estados Unidos começaram a brincar — e a tropeçar — com ele. Charles Sanders Peirce tentou prová-lo nos anos 1860. Arthur Cayley perguntou oficialmente, em 1878, à London Mathematical Society, se alguém já o resolvera, e publicou um texto explicando por que a questão era escorregadia.

Em 1879, o advogado londrino Alfred Bray Kempe anunciou na revista Nature que tinha uma prova. Formado em Cambridge sob influência de Cayley, Kempe usou um argumento engenhoso que ficaria conhecido como cadeias de Kempe. A ideia, em linhas gerais, era esta: suponha um mapa já colorido com quatro cores, faltando apenas uma região final. Se ela não estiver cercada pelas quatro cores, uma delas sobra. Se estiver, Kempe mostrava como trocar cores ao longo de cadeias de regiões adjacentes para liberar uma cor disponível. O raciocínio parecia cobrir todos os casos.

A comunidade celebrou. Kempe foi eleito membro da Royal Society, publicou versões aprimoradas da prova e ganhou prestígio duradouro. O físico escocês P. G. Tait desenvolveu ideias relacionadas, tentando reformular o problema em termos de grafos e ciclos. Mas havia rachaduras. Em 1890, Percy John Heawood mostrou que o argumento de Kempe falhava em certas configurações sutis. A “prova” desmoronou. Ainda assim, do erro nasceu um resultado sólido: Heawood demonstrou que cinco cores sempre bastam. O problema voltava a ser conjectura — mas agora cercado de técnicas novas.

Heawood dedicaria a vida à coloração de mapas, estendendo a pergunta para superfícies como o toro e obtendo a chamada estimativa de Heawood, que relaciona o número de cores à característica de Euler da superfície. Também provou casos especiais do problema plano, como mapas cujas regiões têm números de lados múltiplos de três. Enquanto isso, outros matemáticos começaram a traduzir o problema para a linguagem dos grafos planares: cada região vira um vértice, cada fronteira compartilhada vira uma aresta. Colorir o mapa equivale a colorir os vértices do grafo sem que vizinhos coincidam.

Essa mudança de linguagem permitiu novas ferramentas. Ao adicionar arestas até que todas as faces do grafo fossem triângulos, obtém-se uma triangulação. Dentro dela, matemáticos passaram a estudar configurações locais — pedaços do grafo contidos num contorno fechado. Um conjunto de configurações é dito inevitável se toda triangulação contiver pelo menos uma delas. Uma configuração é redutível se não pode aparecer num contraexemplo mínimo ao teorema das quatro cores. A estratégia passou a ser dupla: encontrar um conjunto inevitável de configurações e provar que todas são redutíveis. Se todo mapa contém uma configuração “inofensiva”, então nenhum contraexemplo pode existir.

Ao longo do século XX, essa abordagem foi refinada. Weinicke, Veblen e, sobretudo, George David Birkhoff desenvolveram o conceito de redutibilidade. Em 1922, Philip Franklin mostrou que mapas com até 25 regiões são 4-coloríveis; outros ampliaram o limite para 27, 35, 39 e depois 95 regiões. Esses resultados não resolviam o problema geral, mas testavam e fortaleciam as técnicas.

A virada conceitual decisiva veio com Heinrich Heesch, em 1969, e seu método de descarregamento. A cada vértice de um grafo planar atribui-se uma “carga” igual a $6 – d$6−d, onde $d$d é o grau do vértice. Pela fórmula de Euler, a soma total das cargas é 12. Heesch mostrou que, redistribuindo cargas segundo regras locais, é possível provar que certas configurações devem aparecer — caso contrário, surgiriam vértices com carga positiva impossível. Ele acreditava que um conjunto inevitável com cerca de 8.900 configurações bastaria. O obstáculo era testar a redutibilidade de tantas peças, algumas grandes demais para os métodos da época.

Em 1976, Kenneth Appel e Wolfgang Haken, na Universidade de Illinois, levaram o plano adiante com ajuda de computadores. Baseados nas ideias de Heesch e no uso de cadeias de Kempe para reduções, construíram um conjunto inevitável com cerca de 1.500 configurações, mantendo os contornos suficientemente pequenos para análise automática. Seguiu-se um longo processo de ajustes, intuição e tentativa e erro na escolha das regras de descarregamento e das configurações. Ao todo, usaram cerca de 1.200 horas de computação — com colaboração de John Koch — para verificar que cada configuração era redutível.

Assim, a conjectura tornou-se teorema pela segunda vez — e desta vez para ficar. Publicado em 1977, marcou a primeira grande prova matemática dependente de cálculos de computador, longos demais para verificação manual completa. Surgiram desconfortos: pode-se confiar numa prova que ninguém lê de ponta a ponta? Aos poucos, verificações independentes, simplificações posteriores e novas versões do algoritmo reduziram as dúvidas. O teorema das quatro cores tornou-se também um marco filosófico.

Hoje, o problema original de Guthrie parece quase ingênuo. Quatro lápis de cor bastam. Mas a jornada até essa simplicidade expôs a complexidade escondida nos limites entre regiões — e nos limites entre humano e máquina na prática matemática. O mapa que começou como passatempo estudantil acabou redesenhando a própria ideia de demonstração.