A solução de Euler

Representação abstracta do mapa da cidade através de um grafo .
As margens e ilhas do rio Pregel são representadas por pontos, ditos os vértices do grafo.
As pontes são representadas através de linhas unindo os vértices. Estas linhas dizem-se as arestas do grafo.



Considere o seguinte caminho percorrendo seis arestas distintas.
Junto de cada vértice vem representado o seu grau, ou valência, relativo ao caminho já percorrido, i.e. o número de arestas já percorridas que incidem nesse vértice.



Conclusões:

• Excetuando os vértices de partida e de chegada todos os restantes têm grau par.
• Os vértices de partida e de chegada têm grau ímpar.
• Quando o vértice de partida coincide com o de chegada, este tem grau par.

Logo, como há três vértices de grau ímpar, não existe nenhum caminho percorrendo todas as arestas e atravessando uma única vez cada uma delas.