Problema das Quatro Cores
Contexto
O problema surgiu em 1852, quando Francis Guthrie, um estudante de matemática, estava colorindo um mapa dos condados da Inglaterra. Ele notou que parecia ser possível colorir qualquer mapa usando apenas quatro cores, de forma que duas regiões com uma fronteira em comum nunca tivessem a mesma cor.
Ele perguntou a seu professor, o famoso matemático Augustus De Morgan, se isso poderia ser provado. Apesar de sua simplicidade aparente, o problema se mostrou incrivelmente difícil de resolver, permanecendo como uma conjectura (uma afirmação matemática que se acredita ser verdadeira, mas que não foi provada) por mais de 120 anos. Muitos matemáticos renomados tentaram e falharam em prová-lo, e diversas “provas” incorretas foram publicadas ao longo do tempo.
Problema
A questão formal é:
Quote
“Qual o número mínimo de cores necessárias para colorir qualquer mapa em uma superfície plana, de modo que duas regiões que compartilham uma fronteira comum (e não apenas um ponto) tenham sempre cores diferentes?”
Na linguagem da Teoria dos Grafos, o problema é traduzido da seguinte forma:
- Cada região do mapa é um vértice (um ponto).
- Se duas regiões compartilham uma fronteira, uma aresta (uma linha) é desenhada entre seus respectivos vértices.
- O ato de colorir o mapa se torna o ato de atribuir uma cor a cada vértice.
Assim, a pergunta se torna:
Question
“É verdade que os vértices de qualquer grafo planar (um grafo que pode ser desenhado em um plano sem que nenhuma aresta se cruze) podem ser coloridos com no máximo quatro cores, de modo que não haja dois vértices adjacentes com a mesma cor?”
Solução
A solução finalmente chegou em 1976 e foi um marco na história da matemática. Os matemáticos Kenneth Appel e Wolfgang Haken, da Universidade de Illinois, provaram que quatro cores são, de fato, sempre suficientes.
No entanto, a forma como eles provaram foi revolucionária e controversa, pois foi a primeira grande prova matemática realizada com o auxílio indispensável de um computador.
A prova foi inicialmente recebida com ceticismo, pois não podia ser verificada manualmente por um ser humano. No entanto, com o tempo e com verificações independentes (usando diferentes programas e hardwares), o Teorema das Quatro Cores foi amplamente aceito pela comunidade matemática.