O "Teorema" das 4 cores é falso!

O "Teorema" das 4 cores tem uma longa história. E também uma longa história de pseudo-demonstrações falhadas, quer por amadores quer por grandes matemáticos. Tim "Nerd" Ragnar parece ter dado uma machadada fatal naquilo que se julgava ser uma demonstração correcta - demonstração a que, curiosamente, os matemáticos mais "puros" sempre torceram o nariz por ser uma demonstração assistida por computador (na verdade, a primeira deste género) e ser impossível a um ser humano verificá-la.


O problema das quatro cores data de 1852, quando Francis Guthrie, na altura estudante de liceu, estava a colorir um mapa dos condados de Inglaterra. Guthrie constatou que, com algum esforço, conseguia colori-lo com a condição de condados contíguos terem cores diferentes usando apenas 4 cores diferentes. Intrigado, foi perguntar ao irmão mais velho, Frederick, já na Universidade, se isto se passava com qualquer mapa.

Frederick Guthrie não conseguiu responder, e foi perguntar ao seu eminente professor em Cambridge, o célebre Augustus de Morgan, se sabia resolver o problema. De Morgan pensou, pensou... e a resposta era não. Tinha nascido o problema das quatro cores.

Aqui começa a história das débâcles matemáticas, que agora tem pelos vistos um novo episódio. A primeira referência na literatura matemática à conjectura das quatro cores deve-se a Arthur Cayley em 1878. Um ano depois aparece a primeira demonstração pelo matemático Kempe; o seu erro foi apontado 11 anos depois por Heawood.

Outra demonstração errada deve-se a Tait, em 1880; o erro no raciocínio foi apontado por Petersen em 1891. Durante estes peiodos a conjectura das quatro cores foi considerada um "Teorema", e é provavelmente por isso que as empresas de lápis de cor (e hoje em dia de canetas para transparências) vendem pacotinhos de 4, e não 3 ou 5, canetas: julgava-se que 4 cores eram suficientes.

Seguiram-se contribuições matemáticas importantes de Birkhoff, que permitiram a Franklin mostrar em 1922 que a conjectura das 4 cores é verdadeira para mapas com, no máximo, 25 regiões.

Mais tarde Heesch introduziu técnicas importantes em teoria de grafos (redutibilidade e descarga) que permitiram a outros matemáticos reduzir a análise do problema a um número finito (embora gigantesco) de casos. Em 1976 os matemáticos Hapel e Akken conseguiram reduzir os casos possíveis a pouco mais de dois milhares e colocaram um computador a verificá-los um a um.

O resultado foi a primeira demonstração assistida por computador. O problema das quatro cores é, assim, um Teorema, embora nunca nenhum ser humano isolado tenha conseguido construir uma demonstração "clássica".

É neste contexto que surge o extraordinário contraexemplo de Ragnar! Não sendo um matemático profissional (e auto-intitulando-se "Nerd"), coloca a circular o contra-exemplo acima de um mapa plano que não se consegue colorir apenas com 4 cores.

A comunidade matemática está chocada. Mais uma demonstração para o lixo. Mas agora com a certeza de que o resultado é falso!

O que se passou mal com esta pseudo-demonstração? Aparentemente há uma subtileza em teoria de grafos que faz com que, tecnicamente, o grafo do mapa apresentado possua vértices imersivamente reduzidos e tal que o grafo dual (harmonicamente conjugado) não possui esta propriedade. Ainda não é claro, na altura da escrita, como é que este facto passou despercebido na "demonstração" por computador. Mas passou!

Aparentemente, o mapa de Ragnar é o menor com esta propriedade patológica, e portanto o mais pequeno contra-exemplo. O leitor é cordialmente convidado a tentar colorir o mapa com 4 cores. Atenção: a região exterior ("oceano") também deve ser colorida com uma das 4 cores.

Nota: pelo seu interesse científico também publiquei este post no De Rerum Natura.