Os moradores de Königsberg (hoje Kaliningrad, na Rússia) se perguntavam se era possível fazer um passeio pela cidade passando exatamente uma vez em cada uma das suas (à época) sete pontes.

Leonard Euler, um grande matemático suíço, deu uma solução elegante e simples para a questão. Para tanto, “traduziu” o problema para a linguagem de grafos. Este resultado, publicado em 1736, é considerado por muitos o primeiro artigo em Teoria dos Grafos. Você pode pensar em um grafo como um conjunto de pontos (vértices) ligados (ou não) por um ou mais traços (arestas).

O problema original das Pontes de Königsberg, ilustrado acima, não tem solução. Repare que, para que o caminho passe exatamente uma vez em cada ponte, as porções de terra onde o passeio se inicia e onde termina são as únicas que podem ter um número ímpar de pontes.

Atualmente, esta teoria desperta grande interesse pelas inúmeras aplicações que possibilita: circuitos elétricos, circulação de mercadorias, transporte, administração de redes etc. Por exemplo, uma rede telefônica ou a internet podem ser tratadas como grafos.

Coloque quantas pontes quiser entre as regiões e tente, com o giz, traçar um caminho que passe por todas as pontes sem repetir nenhuma! Não é necessário voltar ao ponto inicial. Nem sempre esse problema tem solução. Do que isso depende?