Задача
COM-B2-M07-P012 Необходимое условие эйлерова пути
#12
★★★☆☆ Уровень 3 из 5
В связном графе есть путь, проходящий по каждому ребру ровно один раз. Докажите, что число вершин нечётной степени равно \(0\) или \(2\).
Все промежуточные посещения вершины разбивают рёбра на пары вход-выход.
Если путь не замкнут, то у каждой промежуточной вершины использованные рёбра разбиваются на пары: вошли и вышли. Поэтому промежуточные вершины имеют чётные степени. Нечётными могут быть только начало и конец пути.
Если путь замкнут, то у начальной вершины входы и выходы тоже образуют пары, поэтому все степени чётны. Значит, нечётных вершин либо \(0\), либо \(2\).
Нужно для полного критерия эйлерова пути.