Há muitos anos, na cidade de Koenigsberg, actual Kalininegrado na Rússia, os habitantes gostavam de atravessar as sete pontes que ligavam as duas margens do rio que tinha uma ilha no meio. O desafio era passar por todas as pontes sem nunca atravessar nenhuma mais de uma vez. Como não conseguiam, colocaram o problema ao maior matemático da época Leonhard Euler. Que descobriu que se podia aplicar uma regra geral.
Euler simplificou o problema redesenhando vértices e arcos, o que hoje chamamos um grafo. Notou que nenhum vértice por onde se passa pode ter um número impar de arcos, senão temos de voltar a passar por outro arco. Por isso apenas o vértice de partida e o de chegada podem ter grau impar. No caso das pontes de Koenigsberg, há quatro vértices com grau impar logo este enigma não tem solução.