Koenisberg, città della Prussia Orientale, chiamata ora Kaliningrad ed exclave della Russia, famosa per aver dato i natali al filosofo Immnuel Kant ed al matematico David Hilbert, è attraversata dal fiume Preghel, che in città si biforca in due rami dividendo la città in quattro quartieri A,B,C,D, congiunti da 7 ponti come in figura. 
Una leggenda dice che, intorno al 1750, fra gli abitanti della città era sorto il problema se fosse possibile effettuare una passeggiata che partendo da uno qualsiasi dei quattro quartieri vi facesse ritorno, passando una ed una sola volta per ciascun ponte.
Eulero ha il merito di aver formulato il problema in termini di teoria dei grafi, astraendo dalla
situazione specifica di Koenisberg; innanzi tutto eliminò tutti gli aspetti contingenti ad esclusione delle aree urbane delimitate dai bracci fluviali e dai ponti che le collegano; secondariamente rimpiazzò ogni area urbana con un punto, cioè con il nodo di un grafo e i ponti con i lati del grafo stesso.

Eulero rappresentò la disposizione dei ponti congiungendo con altrettante linee le quattro grandi
zone della città. Si noti che dai nodi A,B eD partono ( o arrivano) 3 ponti, dal nodo C invece 5
ponti. Quindi i gradi dei nodi sono rispettivamente 3,3,5,3. Eulero, quindi fu un precursore della
teoria dei grafi anche se la sua dimostrazione non la utilizza in senso effettivo.
Teorema 1
Il problema dei ponti di Koenisberg non ha soluzione.
Dimostrazione di Eulero. Se indichiamo un cammino con i vertici successivi che percorre, il
cammino ABD, percorre due ponti, quindi poiché i ponti sono 7 per trovare un percorso che li
attraversi tutti bisognerebbe scrivere una parola di 8 lettere formata tutta da A,B,C e D. Ma se da un
vertice escono 3 ponti per percorrerli tutti occorre scrivere tale vertice almeno 2 volte nel cammino,
se ne escono 5 invece comparirà almeno 3 volte, in generale un vertice dispari di grado n, deve
essere scritto n/2 + 1 volte.Poiché A,B e D hanno grado 3, devono essere scritti ciascuno 2 volte e
poiché C è di grado 5 deve essere scritto almeno 3 volte. Quindi la parola che indica il cammino
sarà formata da 3+2+2+2=9 lettere e ciò è contro quanto affermato all'inizio.






