Докажите,что если обход графа существует,то количество вершин, из которых выходит нечётное число рёбер, не превосходит 2

Предыдущий
вопрос Следующий
вопрос

Предположим, что существует обход графа, в котором количество вершин с нечетным числом ребер больше 2.

Рассмотрим цикл в этом обходе, который начинается и заканчивается в одной и той же вершине (такой цикл обязательно существует, так как все вершины посещаются ровно по одному разу). Поскольку количество вершин с нечетным числом ребер больше 2, в этом цикле должны быть как минимум 4 вершины с нечетным числом ребер (2 для начальной и конечной вершин и еще 2 для других вершин на цикле).

Рассмотрим подцикл, состоящий только из этих 4 вершин. Этот подцикл также содержит вершины с нечетным числом ребер, и, следовательно, его можно пройти, начав и закончив в разных вершинах подцикла. Таким образом, мы можем построить другой цикл, который начинается и заканчивается в разных вершинах, исходящие из него ребра будут противоречить условию обхода графа.

Следовательно, наше предположение о существовании обхода графа с более чем 2 вершинами с нечетным числом ребер неверно, и мы доказали, что если обход графа существует, то количество вершин с нечетным числом ребер не превосходит 2.