O problema colorido que há muito frustra os matemáticos

14:03
05/05/2023

O problema das quatro cores é simples de explicar, mas sua prova complexa continua a ser celebrada e desprezada.

Você pode resolver isso? Teorema da incompletude de Gödel

Um dos grandes episódios da história da matemática começou em 23 de outubro de 1852. Em uma carta a Sir William Rowan Hamilton, Augustus De Morgan escreveu: “Um aluno meu pediu-me hoje para dar-lhe uma razão para um fato que eu fiz. não sei se era um fato – e ainda não o sei“. Até hoje, esse “fato” continua a encantar e desafiar os estudiosos.

O aluno era Frederick Guthrie, e o “fato” em questão veio originalmente de seu irmão, Francis. Depois de olhar para um mapa dos condados britânicos, ele se perguntou se era sempre possível colorir um mapa usando quatro cores ou menos, garantindo que as regiões que compartilham uma fronteira (mais do que um ponto de canto) tivessem cores diferentes.

Parecia que isso deveria ser sempre possível. “Quanto mais penso nisso, mais evidente parece”, escreveu De Morgan. Ainda assim, o problema não excitou Hamilton. Ele respondeu: “Não é provável que eu tente seu ‘quatérnio de cores’ muito em breve.” E os esforços de De Morgan para atrair o interesse de outros também falharam.

São necessárias quatro cores para colorir a Virgínia Ocidental, Pensilvânia, Ohio, Kentucky, Virgínia e Maryland – três para os vizinhos da Virgínia Ocidental e uma quarta para a própria Virgínia Ocidental.

O problema ficou praticamente inativo até 1878, quando Arthur Cayley perguntou aos membros da London Mathematical Society se alguém havia encontrado uma prova. Logo depois disso, as provas começaram a aparecer. Foi a primeira, do advogado Alfred Kempe em 1879, que se revelou a mais importante. A prova foi convincente e foi aceita como correta por mais de uma década. Infelizmente, a prova de Kempe — como todas as outras que apareceriam no próximo século — era falha. No entanto, era engenhoso e continha ideias-chave que apareceriam na prova final.

Para entender como Kempe e a maioria dos matemáticos encaram esse problema, é importante reconhecer que um mapa contém muitas informações irrelevantes para o problema da coloração, como forma, tamanho e localização exata de cada região. Tudo o que importa é quais regiões compartilham limites, embora exijamos que todas as regiões estejam conectadas; Michigan, com sua península superior separada, na verdade não impede que o mapa dos EUA seja quadricolor, mas poderia, matematicamente.

Para focar nas informações que importam, podemos codificar essas relações usando um grafo, também conhecido como rede, onde pontos (vértices) são conectados por linhas (arestas). Substitua cada região do mapa por um vértice e conecte os vértices das regiões vizinhas com uma aresta. Se ajudar, podemos imaginar que os vértices são as capitais e as arestas são as estradas que as unem.

Dessa forma, o problema de coloração de mapas torna-se um problema de coloração de grafos: pinte os vértices de modo que os vizinhos tenham cores diferentes. O número mínimo de cores é chamado de número cromático do grafo. Podemos perguntar sobre o número cromático de qualquer gráfico, mas gráficos que vêm de mapas têm propriedades especiais. Esses gráficos são simples, o que significa que não há arestas começando e terminando no mesmo vértice (chamadas loops), e dois vértices só podem ser unidos por uma aresta. O gráfico também é planar, o que significa que pode ser desenhado sem que as arestas se cruzem.

Conheça nossos cursos:

Um problema de coloração de mapas pode ser transformado em um problema de coloração de grafos.

Podemos agora reformular o problema de Francis Guthrie: Prove que o número cromático de todo grafo planar simples é no máximo quatro.

Aqui está um esboço do argumento de Kempe, descrito em termos modernos usando gráficos em vez de mapas. Ele começou observando que um grafo com um vértice – talvez o mapa seja uma ilha solitária – requer apenas uma cor. Ele então usou um argumento inteligente para construir a partir daí, argumentando que é possível usar no máximo quatro cores para colorir um grafo com dois vértices, depois três vértices e assim por diante. Veja como.

Suponha que podemos colorir todos os grafos planares simples com n vértices com no máximo quatro cores – isso é trivial para $n$ menor que $5$ – e então recebemos um com $n + 1$ vértices. Como podemos mostrar que também será colorível com no máximo quatro cores?

Primeiro, Kempe mostrou, usando um argumento de contagem cuidadoso, que todo grafo planar simples tem algo em comum: ele deve conter pelo menos um vértice com no máximo cinco vizinhos. Levando em consideração todas as opções, isso significa que todo grafo possível baseado em um mapa contém uma das seis configurações especiais de vértices.

Embora descrito usando mapas e não grafos, Alfred Kempe mostrou que todo grafo planar simples deve ter um vértice de um desses tipos.

Se removermos esse vértice e todas as arestas que se conectam a ele, deixamos para trás um grafo com n vértices — que já sabemos que pode ser colorido com quatro cores. Na verdade, fazemos isso como o próximo passo. Agora, observe os vértices adjacentes ao vértice removido. Se eles exibirem três ou menos cores, podemos colorir o vértice removido com uma das cores restantes e pronto: acabamos de mostrar que o grafo com $n + 1$ vértices pode ser colorido com quatro cores. E se os vértices adjacentes incluírem todas as quatro cores, Kempe desenvolveu um método inteligente de recolorir certos vértices para liberar uma cor para o vértice removido, novamente mostrando que o grafo com $n + 1$ vértices precisa de apenas quatro cores.

Em 1890, o matemático Percy Heawood identificou o erro de Kempe. Houve um caso especial em que o método inteligente de Kempe falhou. Heawood observou que, embora seu próprio trabalho parecesse “destrutivo [em vez] de construtivo”, ele mostrou que a técnica de Kempe poderia provar que todo mapa pode ser colorido com cinco ou menos cores – não exatamente o objetivo original, mas ainda assim impressionante.

Heawood também investigou mapas desenhados em superfícies mais complicadas. Ele provou que um mapa em uma rosquinha com $g$ buracos pode precisar de até $\frac{1}{2}\left ( 7+\sqrt{1+48g} \right )$ cores (onde este valor é arredondado até o inteiro mais próximo). Portanto, decorar um donut comum pode exigir até sete cores de glacê. No entanto, no que estava se tornando um padrão, sua prova para superfícies gerais estava incompleta e não tínhamos uma prova completa até 1968.

Livros que nos recomendamos

Para este mapa em uma rosquinha, mostrado de ambos os lados, cada uma das sete regiões faz fronteira com as outras seis regiões, então são necessárias sete cores.

Mas mesmo quando o teorema de Heawood para superfícies gerais foi provado, o problema das quatro cores permaneceu sem solução. Graças a décadas de trabalho árduo, porém, uma prova estava à vista.

Em uma conferência em 1976, 124 anos depois que Guthrie apresentou o problema, Wolfgang Haken anunciou uma prova em colaboração com Kenneth Appel e com a ajuda do aluno de pós-graduação John Koch. As reações foram mistas. “Eu esperava que o público irrompesse com uma grande ovação“, escreveu Don Albers, que esteve presente na palestra. “Em vez disso, eles responderam com aplausos educados!” Foi porque, em vez de produzir um argumento de lápis e papel, a equipe dependia muito de um computador.

Eles não tinham uma máquina para responder diretamente à pergunta, já que infinitos grafos planares são possíveis e um computador não pode verificar todos eles. No entanto, assim como Kempe provou que todo grafo contém uma das seis configurações especiais de vértices, Appel e Haken mostraram que todo grafo deve ter uma das 1.936 configurações especiais. Provar o teorema equivalia a mostrar que precisamos apenas de quatro cores para colorir qualquer gráfico que contenha esses subgrafos. Dividir os seis casos especiais de Kempe em 1.936 subcasos deu a eles um controle mais refinado e tornou cada caso mais fácil de verificar – embora o número total fosse agora muito grande para um ser humano verificar sem assistência. Na verdade, a conclusão dos cálculos exigiu mais de 1.000 horas de uso do computador.

A comunidade matemática aceitou os resultados apenas de má vontade, acreditando que uma prova deveria ser compreensível e verificável inteiramente por humanos. Embora fosse aceitável que os computadores executassem aritmética de rotina, os matemáticos não estavam preparados para ceder o raciocínio lógico a um dispositivo de computação. Esse conservadorismo e relutância em adotar avanços que economizam tempo não eram novos. No século XVII, houve protestos semelhantes quando alguns matemáticos usaram técnicas algébricas modernas para resolver problemas de geometria. Um drama semelhante pode ocorrer novamente com o surgimento do aprendizado de máquina: os matemáticos aceitarão um teorema descoberto e provado por um algoritmo opaco?

A prova do problema das quatro cores foi, claro, apenas o começo da revolução do computador na matemática. Em 1998, Thomas Hales usou um computador para provar a famosa conjectura de Johannes Kepler de que a maneira mais eficiente de empilhar esferas é aquela empregada rotineiramente para empilhar laranjas em uma mercearia. E, recentemente, os computadores ajudaram a encontrar o “número de Deus” – o número máximo de voltas necessárias para resolver um cubo de Rubik (20 viradas de face ou 26 se as meias voltas contarem como duas).

Embora o problema das quatro cores para mapas esteja resolvido, muitas questões básicas sobre coloração de grafos permanecem sem resposta ou só agora estão sendo resolvidas.

O trabalho de Heawood com superfícies mostrou que podemos fazer perguntas sobre colorabilidade sobre grafos não planares. E, de fato, o número cromático de um gráfico particular não depende da superfície na qual o mapa equivalente é desenhado. Por exemplo, um grafo no qual cada vértice está conectado a todos os outros vértices é chamado de grafo completo, e o número cromático de um grafo completo com $n$ vértices é $n$. Portanto, se um grafo grande contém um grafo completo com n vértices, sabemos que o número cromático do grafo grande é pelo menos $n$.

Um grafo completo com n vértices tem número cromático $n$.

Esta observação não implica que se o número cromático de um grafo é $n$, então ele contém um grafo completo com $n$ vértices. Mas em 1943, Hugo Hadwiger conjecturou algo muito semelhante. Ele acreditava que se um grafo sem loops tem número cromático $n$, então ele tem um arranjo de vértices chamado minor, onde deletar alguns vértices e arestas e agrupar outros resulta em um grafo completo com n vértices. Reformulada, esta conjectura afirma que, se um gráfico não tiver um menor, ele pode ser colorido com menos de $nk_{n}k_{n}$ cores. A conjectura de Hadwiger, um dos problemas em aberto mais importantes da teoria dos grafos, generaliza o teorema das quatro cores, pois um grafo planar não pode conter um menor $k_{5}$.

Embora a coloração de gráficos tenha começado com uma questão de cartografia, problemas que nada têm a ver com mapas ou cores também podem se encaixar na estrutura de coloração de gráficos. Por exemplo, o sudoku é um problema de coloração de gráfico disfarçado. Visualize cada célula como um vértice e os nove dígitos como as cores. Cada vértice tem 20 arestas saindo dele – uma para cada célula em sua linha, em sua coluna e em seu subquadrado de 3 por 3. Este grafo de 81 vértices e 810 arestas começa com uma coloração parcial (as pistas dadas). O objetivo do jogo é colorir o resto dos vértices.

Sudoku pode ser visto como um problema de coloração de gráficos.

Apesar de toda a atenção que esses problemas de coloração receberam, ainda não temos uma prova do teorema original das quatro cores que um ser humano possa ler. Isso não é por falta de tentativa. Ainda hoje surgem novas provas, geram algum entusiasmo e, tal como a prova de Kempe, mostram conter erros.

O matemático Paul Erdős costumava falar sobre “O Livro” — um tomo imaginário contendo as provas mais elegantes de cada teorema. Alguém se pergunta se O Livro contém uma prova legível por humanos do teorema das quatro cores e, se assim for, se algum dia a veremos.

Este artigo foi baseado na publicação de David S. Richeson para a revista Quanta.

A Matemática É Vida pode ajudar seu filho a alcançar a independência no aprendizado, aumentar sua autoestima e torná-lo apaixonado por aprender novas habilidades.