Teorema das Cinco Cores: Dado um mapa num plano, dividido em regiões, é possível colorir cada uma das regiões, de forma a que regiões vizinhas tenham cores diferentes e não usando no total mais de cinco cores.
 
 

Prova:

        Na prova, basta-me considerar o caso de o mapa representar apenas uma ilha. Na verdade, se o mapa de qualquer ilha puder ser pintado com 5 cores, também o mapa de qualquer ilha e o mar envolvente podem ser pintados apenas com 5 cores. Basta pensar na ilha de partida, com mais um país criado acrescentando uma faixa litoral (conquistada ao mar) à volta da ilha original e pintar esta nova ilha com 5 cores: a cor do país envolvente pode ser usada para pintar o mar da ilha original. E, por outro lado, se uma ilha e o mar puderem ser pintados com cinco cores, então um mapa formado por várias ilhas e pelo mar poderá também ser pintado, usando as mesmas cores em cada ilha.Também podemos excluir o caso de haver um país por exemplo em forma de anel, que separe a ilha em duas regiões sem comunicação entre si: num tal caso, poder-se-ia pintar primeiro a ilha formada pelo «anel» e pelos países dentro e depois o novo mapa consistindo nos países de fora e num país que englobava o «anel» com tudo que lhe estava interior, este último com a mesma cor usada antes para o anel.
Se tivermos um mapa em que mais de três países se encontram no mesmo vértice (Fig.1), então podemos desenhar um novo mapa, que será exactamente a cópia do original, excepto no facto de ter um pequeno país novo, formado em volta do vértice em questão (Fig. 2). Este novo país deverá ser suficientemente pequeno, de forma a não “cobrir” por completo nenhuma fronteira.

O novo mapa tem mais um país, tem mais vértices do que o mapa original, mas apenas três países se encontram em cada um dos novos vértices. Assim, o vértice comum a mais de três países foi eliminado. Podemos fazer o mesmo para cada vértice do nosso mapa que tenha em comum mais de três países. Dessa forma, obtemos um novo mapa com mais vértices, mas cada vértice terá apenas três países em comum.

Agora vamos mostrar que se cinco cores são suficientes para colorir o novo mapa (aquele em que cada vértice é comum apenas a três países), então também é possível colorir apenas com 5 cores o mapa original (em que um vértice podia ter mais de três países em comum).

Suponhamos que o mapa em que os vértices são comuns apenas a três países pode ser pintado nas condições do teorema (Fig. 3); então, para pintar o mapa original, basta manter as mesmas cores nos países existentes desde o início e eliminar os novos países formados (Fig. 4).

Este processo não cria nenhuma infracção à regra de coloração, uma vez que dois países que se encontram num vértice, mas não ao longo de uma fronteira, podem ter a mesma cor.

Recapitulando: um vértice é um ponto em que se encontram pelo menos três países, mas acabamos de ver que não precisamos de considerar os mapas em que se encontram mais de três países em cada vértice. Portanto, basta-nos considerar apenas os mapas em que se encontram exactamente três países em cada vértice.

Vamos agora considerar o número de vértices na fronteira de cada país.Seja fn o número de países com n vértices e f o número total de países.

Note-se que, se um dado país não tem vértices ou tem apenas um vértice, então ele tem apenas um país vizinho e então podemos colorir o país com qualquer cor excepto com a cor do vizinho. Como estes países não causam problemas, vamos deixá-los de parte e supor, no resto da prova, que eles não estão presentes.

Temos então, 

     Façamos agora algumas contagens. Vamos começar por contar o número de arestas (fronteiras) existentes no nosso mapa.

Os países com 2 vértices têm duas fronteiras, ao todo temos assim 2f2 arestas. Os países com 3 vértices, têm três fronteiras, ao todo temos assim 3f3 arestas. E assim sucessivamente. Esta contagem irá finalmente considerar todas as fronteiras do nosso mapa. No entanto, cada uma das arestas será contabilizada duas vezes (pelos dois países que a partilham). (Por comodidade de exposição, estamos a incluir como um país o mar que rodeia a nossa ilha e a considerar que também ele é pintado e contado.) Assim, temos

Analogamente, podemos contar o número de vértices existentes no mapa. Mas, nesse caso, cada um dos vértices será contabilizado três vezes (pelos três países que o partilham). Portanto, vamos ter

Das igualdades (2) e (3) vemos que

Pela Identidade de Euler, v + f = a + 2, vem

De (4) chegamos a

Substituindo f e 3v, usando (1) e (3), 

Da igualdade (5), podemos concluir que, para todo o mapa em que apenas três países se encontram no mesmo vértice, existe pelo menos um país com menos de seis vértices. Pois, se tal país não existisse, então não havia países com dois, três, quatro ou cinco vértices, logo f2 = f3 = f4 = f5 = 0. Assim, o membro da esquerda da igualdade (5) seria igual a zero, enquanto o da direita é maior ou igual a 12.

Agora já sabemos que no nosso mapa temos pelo menos um país com menos de 6 vértices: poderá ter 2, 3, 4 ou 5 vértices. Vejamos então cada um destes casos.

        Consideremos o país que tem dois vértices. Se tem dois vértices, então tem duas arestas (que unem os vértices) e, portanto, tem no máximo dois vizinhos. Se tiver dois e removermos uma das fronteiras (fig. 5), o novo mapa terá f-1 países em vez dos f países iniciais. Suponhamos que o novo mapa pode ser pintado com cinco cores, nas condições do teorema:

Ao repormos a fronteira que tiráramos, podemos pintar o país eliminado com uma das três cores que não se utilizaram nos dois países vizinhos.

        Assim, se o mapa com f - 1 países pode ser pintado como pretendemos, o mapa original com f países também pode.

Se o país com dois vértices tivesse um só vizinho, ele envolvê-lo-ia em forma de anel, o que excluímos acima.
 

        Se tem três vértices, então tem três arestas (que unem os vértices) e, portanto, tem no máximo três vizinhos. E, pelo mesmo raciocínio anterior, tem mais do que um vizinho, portanto pelo menos um deles só tem uma aresta como fronteira comum. Analogamente ao primeiro caso, retiramos essa fronteira do país que tem os três vértices (Fig. 8). Supondo que o novo mapa com f – 1 países pode ser pintado nas condições do teorema (Fig. 9), repomos depois a fronteira e pintamos o país que tinha sido eliminado, com uma das duas cores que não foi utilizada nos seus dois ou três vizinhos (Fig. 10).

        Desta forma, se o mapa com f – 1 países podia ser pintado com apenas as cinco cores nas condições determinadas, então o mapa original com f países também podia.

        Argumentando da mesma forma, vemos que sobra uma cor para pintar o país a que retirámos a fronteira, desde que tenhamos utilizado quatro cores diferentes para os quatro países vizinhos. Mas surge uma dificuldade neste caso. Um dos países vizinhos pode ter duas fronteiras em comum com o mesmo país, como podemos ver na figura seguinte

        Se removermos uma das fronteiras entre P e P2 temos que remover a outra, pois uma fronteira não pode separar um país de si próprio: não é esta a ideia que temos de fronteira. Assim, surge um país com duas fronteiras completamente separadas e em forma de anel. No entanto, podemos evitar a formação do anel: se P e P2 formam um anel, então, como estamos no plano, as outras duas fronteiras de P deverão pertencer a outros dois países que estão separados pelo anel. Logo, esses dois países P1 e P3 são diferentes e não têm nenhuma fronteira em comum. Removemos as fronteiras que separam P de P1 e de P3 e obtemos um novo mapa com f – 2 países. Supondo que este mapa com menos de f países pode ser pintado como pretendemos, será utilizada uma cor para P1 (com P e P3 anexados) e outra para P2. Ao repormos as fronteiras, voltando ao país inicial, utilizamos para P uma das três cores que não foram utilizadas nos seus vizinhos: diferente, pois, das de P1 (e P3) e de P2. Logo, podemos pintar o mapa original como pretendemos.
 

        As mesmas dificuldades podem surgir em formas mais complicadas. Um dos países pode ter duas fronteiras em comum com P (Fig. 12) ou então poderão formar-se outros anéis (Fig. 13).

        Em ambos os casos, como também no caso em que não há formação de anel, o país P tem dois vizinhos, P1 e P3, que não têm nenhuma fronteira em comum entre eles.

        Removemos então as fronteiras de P com P1 e P3. O novo mapa que se obtém tem f – 2 países. Supondo que o novo mapa pode ser colorido com cinco cores nas condições pretendidas, então, como P, P1 e P3 estão agora a formar apenas um país, terão a mesma cor, P2 terá outra, P4 outra e P5 outra. Assim já utilizámos quatro cores. Ao repormos as fronteiras podemos pintar o país P com a cor que sobrou. E, assim, o mapa com f países pode ser pintado obedecendo às condições do teorema.
 

        Como vimos, todo o mapa se insere num destes quatro casos. Logo, o processo de redução está completo. Todo o mapa pode ser reduzido a menos países, com a eliminação de uma ou duas fronteiras. E, se o mapa reduzido puder ser colorido nas condições do teorema, o original também pode. Assim, basta repetir o processo de redução até obtermos um mapa com apenas cinco países. E um mapa com cinco países pode, trivialmente, ser pintado nas condições do teorema. O mesmo é verdadeiro para cada mapa que se obtém ao longo do processo de redução, logo também é válido para o mapa original.

        O que conclui a prova do Teorema das Cinco Cores.