Um mapa plano pode conter centenas de regiões com fronteiras complicadas, mas quatro cores sempre bastam para que regiões vizinhas tenham cores diferentes. A afirmação parece uma brincadeira, mas resistiu por mais de um século e mudou a maneira como produzimos provas matemáticas.
Imagine que você precise colorir um mapa político sem repetir a mesma cor em duas regiões que compartilham um trecho de fronteira. Quantas cores serão necessárias? Quatro, sob as condições usuais do problema, são suficientes.
O resultado é conhecido como Teorema das Quatro Cores. O desafio histórico não era observar que quatro pareciam funcionar em muitos mapas. Era demonstrar que nenhum mapa plano possível exigiria uma quinta cor.
Uma pergunta de 1852
A questão foi formulada por Francis Guthrie ao observar mapas dos condados da Inglaterra. Nas décadas seguintes, diversos matemáticos tentaram apresentar uma demonstração geral.
Em 1879, Alfred Kempe publicou uma prova aparentemente definitiva. Mas Percy Heawood encontrou uma falha em 1890. A tentativa fracassou, embora parte de suas ideias tenha ajudado na prova de que cinco cores sempre são suficientes.
Só em 1976 Kenneth Appel e Wolfgang Haken apresentaram uma demonstração das quatro cores com auxílio computacional, apoiada em trabalho sobre configurações de grafos.
O intervalo de mais de um século entre a pergunta e a resposta mostra que uma afirmação fácil de entender pode exigir Matemática profunda.
De mapas para grafos
Para estudar o problema, substituímos cada região do mapa por um vértice. Ligamos dois vértices quando as regiões correspondentes compartilham um trecho de fronteira.
A representação resultante é um grafo. O objetivo torna-se atribuir cores aos vértices de maneira que vértices conectados não recebam a mesma cor.
O menor número de cores necessário para um grafo G é seu número cromático, representado por χ(G).
Para grafos planares sem laços, o Teorema das Quatro Cores afirma:
A palavra planar é essencial: um grafo planar pode ser desenhado no plano sem cruzamentos de arestas fora dos vértices. Redes abstratas não planares podem exigir mais cores.
Por que cinco regiões não podem ser todas vizinhas?
Uma tentativa intuitiva de construir um contraexemplo seria desenhar cinco regiões em que cada uma fosse vizinha das outras quatro. Essa estrutura corresponde ao grafo completo K₅.
Ele possui cinco vértices e dez arestas. Entretanto, um grafo planar simples com pelo menos três vértices satisfaz:
Para V = 5, temos E ≤ 9. Logo, K₅ não é planar, pois possui dez arestas.
Isso elimina uma construção óbvia, mas não prova o teorema. Um mapa poderia, em princípio, exigir cinco cores sem conter cinco regiões mutuamente vizinhas.
A fórmula de Euler
Para um grafo planar conectado, a relação entre vértices, arestas e faces é:
A fórmula de Euler permite demonstrar restrições importantes. A partir dela, obtemos E ≤ 3V − 6 para grafos planares simples com V ≥ 3.
Pelo lema do aperto de mãos, a soma dos graus dos vértices é 2E. Portanto, o grau médio é menor que seis, o que garante a existência de pelo menos um vértice com grau menor ou igual a cinco.
Essa conclusão é uma peça importante de provas por indução e recoloração.
Por que cinco cores são mais fáceis?
Remova temporariamente um vértice de grau até cinco. Colora o grafo restante. Se o vértice possuir no máximo quatro vizinhos, uma quinta cor estará necessariamente disponível.
Quando ele possui cinco vizinhos, cadeias de Kempe permitem reorganizar cores sob condições apropriadas. Desse raciocínio resulta o Teorema das Cinco Cores.
Mas reduzir cinco para quatro é muito mais complicado. Um vértice com cinco vizinhos pode encontrar as quatro cores já utilizadas. Recolorir uma parte do grafo pode produzir conflitos em outra.
A dificuldade envolve a estrutura global das conexões, não apenas um vértice isolado.
A prova que precisou de computador
Appel e Haken consideraram um possível contraexemplo mínimo: um grafo planar que exigiria cinco cores, embora todos os grafos planares menores fossem coloríveis com quatro.
A estratégia consistiu em construir um conjunto inevitável de configurações locais e demonstrar que cada uma delas era redutível, isto é, incompatível com a existência do contraexemplo mínimo.
A segunda etapa exigia uma grande quantidade de verificações combinatórias. O computador foi usado para examinar casos que seriam impraticáveis de conferir manualmente, seguindo os argumentos da prova.
Se todo contraexemplo mínimo tivesse de conter uma configuração redutível, ele não poderia existir. Portanto, quatro cores bastariam.
Uma prova que ninguém verifica inteira à mão?
O resultado provocou debate sobre o significado de demonstração matemática. Tradicionalmente, imaginamos uma prova como uma sequência de argumentos que uma pessoa pode conferir passo a passo.
Mas como lidar com milhares de verificações realizadas por software? Podemos entender a estratégia geral e ainda depender de máquinas para checar determinados casos.
Em 1997, Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas apresentaram uma demonstração aperfeiçoada. Posteriormente, Georges Gonthier formalizou uma prova no assistente Coq, com verificações mecânicas de etapas lógicas.
Isso não elimina toda dependência de implementações computacionais, mas oferece um novo modelo de rigor: verificadores relativamente pequenos podem checar grandes objetos formais.
O que o teorema não afirma
A conclusão vale para mapas planos com regiões conexas e adjacência por fronteira compartilhada. Regiões que apenas se tocam em um ponto não são consideradas vizinhas no sentido clássico. Também precisamos manter o modelo planar.
Além disso, o teorema garante que uma coloração existe. Ele não afirma que qualquer sequência de escolhas de cores funcionará.
A distinção entre provar existência e construir uma solução eficiente aparece em outras áreas da Matemática, como no problema de doze moedas e três pesagens.
Um mapa revela um problema mais profundo
Transformar regiões em grafos permite revelar propriedades estruturais escondidas pela aparência geográfica. A mesma mudança de linguagem ocorre no artigo Todo mapa distorce o mundo, embora ali o problema trate da geometria de superfícies.
A ligação entre modelos e decisões também é importante em O recurso mais valioso de uma empresa pode não ter preço.
A história das quatro cores mostra que a complexidade de um problema não pode ser medida apenas pela simplicidade de seu enunciado. Também mostra que ferramentas computacionais podem expandir nossa capacidade de verificar provas, sem substituir a necessidade de critérios lógicos rigorosos.
Se aceitamos como verdadeiro um teorema cuja demonstração completa exige milhares de verificações computacionais, o que exatamente significa compreender uma prova?
Livro recomendado
O Livro da Matemática, da DK (ISBN 9786555670233), reúne episódios históricos e conceitos ilustrados da Matemática. Consultar na Amazon Brasil — link afiliado. Confirme edição e disponibilidade.
Fontes acadêmicas
University of Illinois — Four Color Theorem Resources; Robertson, Sanders, Seymour e Thomas, The Four-Colour Theorem, Journal of Combinatorial Theory, Series B (1997), DOI 10.1006/jctb.1997.1750.
Guilherme Augusto Pianezzer
Professor de Matemática, autor e criador de conteúdo. Os textos deste site são produzidos com foco em rigor conceitual, clareza didática e conexão entre Matemática, Economia, Ciência e Educação.
Deixe um comentário