Tout d'abord, Euler a souligné que le choix de la route à l'intérieur de chaque masse terrestre n'a pas d'importance. La seule propriété importante d'un itinéraire est l'ordre dans lequel les ponts sont franchis. Il a donc modifié le problème en termes abstraits. Cela a jeté les bases de la théorie des graphes. Il a supprimé toutes les caractéristiques sauf la liste des masses terrestres et les ponts qui les relient. Dans le langage de la théorie des graphes, il a remplacé chaque masse terrestre par un "sommet" ou un nœud abstrait. Puis il a remplacé chaque pont par une connexion abstraite, une "arête". Une arête (route) enregistrait les deux sommets (masses terrestres) qui étaient reliés. De cette façon, il a formé un graphique.
→ →
Le graphique dessiné est une image abstraite du problème. Ainsi, les bords peuvent être joints de n'importe quelle manière. Seul le fait que deux points soient reliés ou non est important. Changer l'image du graphique ne change pas le graphique lui-même.
Ensuite, Euler a observé que (sauf aux extrémités de la marche), chaque fois que l'on entre dans un sommet par un pont, on le quitte par un pont. Dans toute marche du graphique, le nombre de fois que l'on entre dans un sommet est égal au nombre de fois que l'on en sort. Si chaque pont a été franchi exactement une fois, il s'ensuit que, pour chaque masse terrestre (à l'exception de celles choisies pour le départ et l'arrivée), le nombre de ponts touchant cette masse terrestre doit être pair. En effet, s'il y a n ponts, il est franchi exactement 2n fois. Cependant, les quatre masses terrestres du problème initial sont toutes touchées par un nombre impair de ponts (un pont est touché par 5 ponts, et chacun des trois autres par 3). Il y a tout au plus deux masses qui peuvent être les points d'arrivée d'une marche. Ainsi, la proposition d'une marche traversant chaque pont une fois conduit à une contradiction.
En langage moderne, Euler montre que la possibilité ou non de parcourir un graphe en franchissant une fois chaque arête dépend des degrés des nœuds. Le degré d'un nœud est le nombre d'arêtes qui le touchent. Euler montre qu'une condition nécessaire pour la marche est que le graphe soit connecté et ait exactement zéro ou deux nœuds de degré impair. Ce résultat énoncé par Euler a été prouvé par la suite par Carl Hierholzer. Une telle marche est maintenant appelée chemin eulérien ou marche d'Euler. S'il y a des nœuds de degré impair, alors tout chemin eulérien commence à l'un d'entre eux et se termine à l'autre. Comme le graphique représentant le Königsberg historique comporte quatre nœuds de degré impair, il ne peut pas avoir de chemin eulérien.
Le travail d'Euler a été présenté à l'Académie de Saint-Pétersbourg le 26 août 1735. Il a été publié sous le titre Solutio problematis ad geometriam situs pertinentis (La solution d'un problème relatif à la géométrie de la position) dans la revue Commentarii academiae scientiarum Petropolitanae en 1741. Il est disponible en anglais dans The World of Mathematics.
