Во-первых, Эйлер указал, что выбор маршрута внутри каждого массива суши не имеет значения. Единственным важным свойством маршрута является порядок пересечения мостов. Таким образом, он перевел проблему в абстрактные термины. Это заложило основы теории графов. Он убрал все характеристики, кроме списка массивов суши и мостов, соединяющих их. На языке теории графов он заменил каждый массив суши абстрактной "вершиной" или узлом. Затем он заменил каждый мост абстрактным соединением, "ребром". Ребро (дорога) фиксировало, какие две вершины (массивы суши) были соединены. Таким образом, он сформировал граф.
→
→ 
Нарисованный граф является абстрактным изображением проблемы. Поэтому ребра могут быть соединены любым способом. Важно только то, соединены две точки или нет. Изменение изображения графа не меняет сам граф.
Далее Эйлер заметил, что (за исключением конечных точек прогулки), всякий раз, когда человек входит в вершину по мосту, он выходит из нее по мосту. В любой прогулке по графу количество входов в вершину равно количеству выходов из нее. Если каждый мост был пересечен ровно один раз, то из этого следует, что для каждого участка суши (кроме тех, которые выбраны для старта и финиша) количество мостов, касающихся этого участка, должно быть четным. Это объясняется тем, что если существует n мостов, то его пересекают ровно 2n раз. Однако все четыре массива суши в исходной задаче имеют нечетное количество мостов (один из них имеет 5 мостов, а каждый из трех других - по 3). Существует не более двух массивов, которые могут быть конечными точками прогулки. Таким образом, предложение о том, что пешеход пересекает каждый мост один раз, приводит к противоречию.
Выражаясь современным языком, Эйлер показал, что возможность или невозможность пройти по графу, пересекая каждое ребро один раз, зависит от степеней узлов. Степень узла - это количество ребер, касающихся его. Эйлер показывает, что необходимым условием для прохождения графа является то, чтобы он был связным и имел ровно ноль или два узла нечетной степени. Этот результат Эйлера был позже доказан Карлом Гирхольцером. Такая прогулка теперь называется эйлеровым путем или прогулкой Эйлера. Если есть узлы нечетной степени, то любой эйлеровский путь будет начинаться в одном из них и заканчиваться в другом. Поскольку граф, представляющий исторический Кенигсберг, имеет четыре узла нечетной степени, он не может иметь эйлерова пути.
Работа Эйлера была представлена Санкт-Петербургской академии 26 августа 1735 года. Она была опубликована под названием Solutio problematis ad geometriam situs pertinentis (Решение задачи, относящейся к геометрии положения) в журнале Commentarii academiae scientiarum Petropolitanae в 1741 году. На английском языке она доступна в журнале The World of Mathematics.
