Задача
COM-B2-M07-P018 Критерий эйлерова пути
Докажите, что связный граф имеет путь, проходящий по каждому ребру ровно один раз, тогда и только тогда, когда число вершин нечётной степени равно \(0\) или \(2\).
Необходимость уже известна. Для двух нечётных вершин добавьте между ними новое ребро.
Необходимость доказана через пары вход-выход: нечётными могут быть только начало и конец незамкнутого эйлерова пути, а у цикла нечётных вершин нет.
Докажем достаточность. Если нечётных вершин нет, то по лемме о чётных степенях в связном графе есть эйлеров цикл.
Если нечётных вершин ровно две, обозначим их \(a\) и \(b\). Добавим новое ребро \(ab\). Теперь все степени стали чётными, поэтому в новом графе есть эйлеров цикл. Удалим из этого цикла добавленное ребро. Оставшаяся последовательность рёбер является эйлеровым путём исходного графа от \(a\) к \(b\).
Полный критерий эйлерова пути уровня Book 2.