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

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

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

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