No início do século 18, a cidade prussiana de Königsberg dividia-se em quatro regiões separadas por braços do rio Pregel: as duas margens, a ilha de Kneiphof, e o bairro de Lomse. Ligando-as, havia sete pontes: Kneiphof tinha duas pontes para cada margem, Lomse tinha uma para cada margem, e a sétima ponte ligava Kneiphof a Lomse.

Não sabemos como nem quando surgiu a pergunta: é possível fazer um passeio pelas quatro regiões cruzando cada ponte apenas uma vez? O grande Leonhard Euler resolveu o problema, em 1735, do seguinte modo:

De cada vez que o passeio passa por uma das regiões, são cruzadas duas pontes: uma para entrar, outra para sair. Então, tirando as regiões de partida e de chegada, todas as demais precisam ser servidas por um número par de pontes. Mas em Königsberg todas as regiões tinham um número ímpar de pontes: 5 em Kneiphof e 3 em cada uma das outras. Logo, não podia existir o passeio solicitado.

Um aspecto crucial do raciocínio de Euler é a abstração: os detalhes são irrelevantes, tudo o que importa são as regiões, que podemos representar como pontos, e as pontes, que podemos representar como linhas ligando esses pontos. Tais configurações, formadas por um certo número de pontos ligados, aos pares, por linhas, são chamados "grafos".

Outro aspecto chave é a generalidade: o teorema de Euler aplica-se a qualquer grafo, não apenas ao grafo de Königsberg: existe um passeio euleriano (ou seja, que cruza cada linha exatamente uma vez) se e somente se, tirando os pontos de partida e de chegada, todos os demais são servidos por um número par de linhas.

A teoria dos grafos é uma das áreas mais produtivas da matemática dos nossos dias e tem inúmeras aplicações práticas, em áreas como desenho de circuitos elétricos, gestão de redes (inclusive internet e redes sociais), estudo do cérebro, modelagem de fenômenos sociais, logística de transportes, planejamento urbano e muitos outros, que movimentam segmentos bilionários da economia.

Duas das pontes foram destruídas na Segunda Guerra Mundial. As demais estão nos locais originais (três são reconstruções). Por isso, atualmente cada uma das margens é servida por apenas duas pontes. Logo, agora é possível fazer passeios eulerianos em Königsberg, desde que comecem em Kneiphof e terminem em Lomse, ou vice-versa.

Só que não é mais Königsberg: ao final da guerra a cidade foi integrada à Rússia e passou a chamar-se Kaliningrado. E o nome do rio também mudou para Pregola.