Метод Эйлера при решении задач на графы заключается в использовании чётности или нечётности числа исходящих из вершины рёбер. 4

Например, в задаче о семи мостах Кёнигсберга нужно было определить, можно ли пройти каждый мост по одному разу и вернуться в исходное место. 45 Эйлер предложил рассматривать мосты в качестве рёбер графа, а земельные участки в виде вершин графа. 4

Ученый доказал общее утверждение: 2

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

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

Алгоритм решения задач с использованием метода Эйлера: 1

1. Нарисовать граф, где вершины — острова и берега, а рёбра — мосты. 1
2. Определить степень каждой вершины и подписать возле неё. 1
3. Посчитать количество нечётных вершин. 1
4. Определить, возможен ли обход: 1

• Если все вершины — чётные, то обход возможен, и его можно начать с любого участка. 1
• Если 2 вершины — нечётные, то обход возможен, но его нужно начать с одной из нечётных вершин. 1

1. Сделать вывод. 1
2. Указать начало и конец пути. 1