Задача о кенигсбергских мостах — старинная математическая задача, в которой требовалось придумать прогулку по городу Кенигсберг (ныне Калининград), чтобы пересекать каждый из семи мостов один и только один раз. 14

Решение задачи было найдено Леонардом Эйлером в 1736 году. 14 Учёный доказал, что проблема не имеет решения. 1 Он указал, что выбор маршрута внутри каждого массива суши не имеет значения, а единственной важной особенностью маршрута является последовательность пересечённых мостов. 1

Связь с теорией графов заключается в том, что Эйлер переформулировал проблему в абстрактных терминах, заложив основы теории графов. 1 В современных терминах каждый массив суши заменяется абстрактной «вершиной» или узлом, а каждый мост — абстрактным соединением, «ребром». 1

Эйлер также вывел критерий существования обхода у графа: граф должен быть связным и каждая его вершина должна быть инцидентна чётному числу рёбер. 5 Поскольку в графе кенигсбергских мостов все вершины были нечётными, то невозможно пройти по всем мостам, не проходя ни по одному из них дважды. 2