În primul rând, Euler a arătat că alegerea traseului în interiorul fiecărei mase de uscat nu are importanță. Singura proprietate importantă a unui traseu este ordinea în care sunt traversate podurile. Astfel, el a schimbat problema în termeni abstracți. Acest lucru a pus bazele teoriei grafurilor. A eliminat toate caracteristicile, cu excepția listei de mase terestre și a podurilor care le conectează. În limbajul teoriei grafurilor, a înlocuit fiecare masă de pământ cu un "vertex" sau nod abstract. Apoi a înlocuit fiecare pod cu o conexiune abstractă, o "muchie". O muchie (drum) a înregistrat ce două verigi (mase de pământ) erau conectate. În acest fel, el a format un graf.
→
→ 
Graficul desenat este o imagine abstractă a problemei. Așadar, marginile pot fi unite în orice mod. Este important doar dacă două puncte sunt conectate sau nu. Schimbarea imaginii graficului nu schimbă graficul în sine.
În continuare, Euler a observat că (cu excepția punctelor finale ale plimbării), ori de câte ori se intră într-un vertex printr-un pod, se părăsește vertexul printr-un pod. În orice parcurs al grafului, numărul de intrări într-un vertex este egal cu numărul de ieșiri din el. Dacă fiecare pod a fost traversat exact o dată, rezultă că, pentru fiecare masă de pământ (cu excepția celor alese pentru început și sfârșit), numărul de poduri care ating masa de pământ trebuie să fie par. Acest lucru se datorează faptului că, dacă există n poduri, aceasta este traversată exact de 2n ori. Cu toate acestea, toate cele patru mase de pământ din problema inițială sunt atinse de un număr impar de poduri (unul dintre ele este atins de 5 poduri, iar celelalte trei sunt atinse de câte 3 poduri). Există cel mult două mase care pot fi punctele finale ale unei plimbări. Așadar, propunerea ca o plimbare să traverseze fiecare pod o singură dată duce la o contradicție.
În limbaj modern, Euler arată că este posibilă sau nu o plimbare printr-un graf care traversează fiecare muchie o dată, în funcție de gradele nodurilor. Gradul unui nod este numărul de muchii care îl ating. Euler arată că o condiție necesară pentru plimbare este ca graful să fie conectat și să aibă exact zero sau două noduri de grad impar. Acest rezultat enunțat de Euler a fost demonstrat ulterior de Carl Hierholzer. Un astfel de traseu se numește acum traseu Eulerian sau traseu Euler. Dacă există noduri de grad impar, atunci orice cale Euleriană va începe la unul dintre ele și se va termina la celălalt. Deoarece graful care reprezintă Königsbergul istoric are patru noduri de grad impar, nu poate avea o traiectorie euleriană.
Lucrarea lui Euler a fost prezentată Academiei din Sankt Petersburg la 26 august 1735. Ea a fost publicată ca Solutio problematis ad geometriam situs pertinentis (Soluția unei probleme referitoare la geometria poziției) în revista Commentarii academiae scientiarum Petropolitanae în 1741. Ea este disponibilă în limba engleză în The World of Mathematics.
