Эйлеровы графы связаны с задачей о Кёнигсбергских мостах через решение, которое её разрешило. 12

В 1736 году Леонард Эйлер заинтересовался этой задачей и доказал, что пройти по каждому из семи мостов ровно один раз невозможно, откуда бы путник ни начинал свой путь. 1

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

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