Conta-se que, no século XVIII, havia sete pontes cruzando o rio Pregel, que banhava a pequena cidade universitária prussiana de Königsberg, hoje Kaliningrad, Rússia. Quatro delas ligavam as margens opostas a uma pequena ilha formada nesse rio, outras duas ligavam as margens opostas a uma outra ilha, próxima à primeira, e a última ponte ligava as duas ilhas, conforme a figura. Os habitantes de Königsberg costumavam passear na sua cidade nas tardes ensolaradas de Domingo, mas nunca tinham conseguido dar um passeio especial que seria Sair de casa, atravessar todas as pontes uma só vez e regressar a casa. No entanto a dúvida quanto à possibilidade persistia.
O matemático Euler (pronúncia: Óilér), em 1735, conseguiu provar, com clareza, que não era possível dar o tal passeio. Para demonstrar esta impossibilidade apresentou à Academia de Ciências Russa de São Petersburgo um diagrama em que fazia a seguinte analogia: à terra, representada pelas duas margens, e às duas ilhas, associou quatro pontos; às sete pontes, associou sete linhas. O diagrama era algo parecido com o da figura ao lado:
Feita tal associação, o problema das sete pontes ficou restrito a traçar o diagrama descrito, com um movimento contínuo, sem levantar o lápis do papel e sem traçar uma linha mais de uma vez.
A, B, C e D são os pontos associados à terra, que é representada pelas duas margens e as duas ilhas. São assinaladas as linhas associadas às sete pontes. Um diagrama desse tipo é simplesmente um esquema consistindo num número finito de pontos, chamados vértices, e num determinado número de linhas. Os vértices são as extremidades das linhas e nenhuma linha tem qualquer ponto comum com uma outra, exceto o vértice comum. Um vértice é par ou ímpar, conforme o número de linhas que o formam seja par ou ímpar. Um diagrama é atravessado passando-se por todas as linhas exatamente uma vez.
Euler baseou-se nas seguintes descobertas que fez:
1- Se um diagrama contém somente vértices pares, ele pode ser atravessado começando e acabando no mesmo ponto.
2- Se um diagrama contém, no máximo, dois vértices ímpares, ele também pode ser atravessado, mas não é possível voltar ao ponto de partida.
3- Se o diagrama contém 2n vértices ímpares, onde n é um número inteiro qualquer, para atravessá-lo será necessário n passagens distintas por uma mesma linha.
No diagrama da figura, que representa o passeio pelas sete pontes de Königsberg, os quatro vértices são todos ímpares, pois são extremidades de um número ímpar de linhas. Assim, como 2n = 4, n = 2 e serão necessárias duas passagens do lápis por uma das linhas para atravessar o diagrama.
Pelo que não é possível efectuar o referido passeio, de modo a passar por todas as sete pontes, saindo de um ponto e retornando lá, sem cruzar mais de uma vez a mesma ponte.
