As sete pontes de Königsberg

Durante muito tempo, os habitantes da cidade de Königsberg, no século XVIII, tentaram resolver um enigma: a cidade é cortada pelo rio Pregel, que forma duas ilhas. Ao todo, sete pontes atravessam esse rio e levam às ilhas. Será possível, em um único passeio de domingo, atravessar todas as pontes, mas cada uma exatamente uma vez? Veja como as pontes estavam dispostas sobre o rio:

Será que conseguimos começar o passeio em algum ponto e atravessar todas as pontes exatamente uma vez? Podemos tentar: começamos embaixo, à esquerda, seguimos para cima e depois, aos poucos, para a direita, assim:

Vemos que atravessamos seis das sete pontes e deixamos uma de lado. Podemos tentar outro caminho…

De novo, atravessamos apenas seis das sete pontes de Königsberg. Quase parece que é impossível atravessar cada ponte exatamente uma vez em um único passeio. Um dia, o famoso matemático Leonhard Euler se deparou com esse problema. E que “famoso”, que nada — Euler foi uma verdadeira lenda da matemática, e até um número leva o seu nome: o número de Euler. Euler decidiu que ia decifrar esse enigma. Ele começou dando nomes às ilhas e às partes da cidade ligadas pelas pontes:

Então, Euler fez o seguinte raciocínio: se uma ilha tem um número par de pontes, podemos atravessar todas essas pontes em um único passeio, não importa onde comecemos. Em suma, chegamos à ilha por uma ponte e saímos por outra — e o número de pontes que ainda falta atravessar diminui em dois. Para poder chegar à ilha por uma ponte e sair por outra, precisamos de duas pontes. Se a ilha tem seis pontes, visitamos a ilha três vezes. Por exemplo, imagine que a ilha B tivesse quatro pontes, assim:

Então poderíamos atravessar todas as pontes em um único passeio de domingo, não importa onde começássemos. Experimente! Na figura, marquei um dos caminhos possíveis. Agora imagine que houvesse ainda mais uma ponte, entre a ilha B e a ilha D:

Vemos que o caminho que escolhemos não nos permite atravessar todas as pontes exatamente uma vez. Teríamos de voltar para a ilha B por alguma ponte e só então seguir para a ilha D. Mas podemos escolher outro caminho. Podemos começar o passeio na ilha B e, assim, conseguimos atravessar todas as pontes exatamente uma vez:

Começamos o passeio na ilha B, subimos até a região A, voltamos por uma ponte até B, seguimos até a região C, voltamos de novo para a ilha B e, por fim, vamos para a ilha D. Ou seja, se começarmos em uma ilha que tem um número ímpar de pontes, conseguimos atravessar todas as pontes dela exatamente uma vez. Ou podemos fazer exatamente o contrário — começar na ilha D e terminar na ilha B.

Assim, Euler percebeu que, para ser possível atravessar todas as pontes exatamente uma vez, é preciso que todas as ilhas tenham um número par de pontes ou que haja duas ilhas com um número ímpar de pontes — começamos em uma das ilhas com número ímpar de pontes e terminamos na outra. Todas as demais ilhas precisam ter um número par de pontes. Vejamos as sete pontes originais de Königsberg:

Vemos que todas as ilhas têm um número ímpar de pontes! A ilha A tem 3, B tem 5, C tem 3 e D também tem 3. Por isso o enigma não tem solução — não é possível atravessar as sete pontes exatamente uma vez em um único passeio de domingo. Se derrubássemos qualquer uma das pontes, o enigma passaria a ter solução. Derrubemos, por exemplo, uma das pontes entre as ilhas B e C:

Vemos que, de repente, a ilha B passa a ter 4 pontes e a ilha C passa a ter duas. O número de pontes das regiões A e D não mudou. Agora temos duas ilhas com um número par de pontes e duas ilhas com um número ímpar de pontes. Se começarmos o passeio em uma das ilhas que têm um número ímpar de pontes, conseguimos atravessar todas as pontes exatamente uma vez. Na figura, começamos na ilha A e terminamos na ilha D.

Assim, Leonhard Euler resolveu mais um famoso problema matemático e, mais ou menos, lançou as bases do que hoje chamamos de teoria dos grafos. Em homenagem a ele, na linguagem da teoria dos grafos, um grafo em que é possível percorrer todas as arestas exatamente uma vez é chamado de grafo euleriano.