|proof=
Докажем эту теорему, используя индукцию по числу вершин <tex>n</tex>.
База индукции: <tex>n = 0</tex> цикл существует.
При <tex>k < n</tex> доказано.
Рассмотрим граф <tex>G = (V, E) </tex> в котором количество вершин с четной степенью больше нуля. Рассмотрим произвольную вершину <tex>u</tex>. Из нее выходит ребро. Пойдем по нему и будем действовать далее также. Таким образом можно дойти до <tex>u</tex> и найти цикл. Выкинем ребра цикла из графа. Первое условие сохранится. Второе может не выполниться, найдём эйлеров цикл в каждой получившейся компоненте связности.
Восстановить Предположим что граф имеющий менее <tex>n</tex> вершин содержит эйлеров цикл исходного . Рассмотрим граф <tex>G = (V, E) </tex> с <tex>n > 0</tex> вершинами, степени которых четны. Допустим, что <tex>v1</tex> и <tex>v2</tex> - вершины графа . Поскольку граф связный, то существует путь из <tex>v1</tex> в <tex>v2</tex>. Поскольку степень <tex>v2</tex> - чётная, существует неиспользованное ребро, по которому можно следующим образом: идём по первому циклупродолжить путь. Поскольку граф конечный, то путь, в конце концов, должен вернуться в <tex>v1</tex>, и эйлеров цикл можно считать построенным. Если <tex>с1</tex> является эйлеровым циклом для <tex>G</tex>, тогда доказательство закончено. Если нет, то пусть <tex>G'</tex> - подграф графа <tex>G</tex>, полученный удалением всех рёбер, принадлежащих <tex>c1</tex>. Поскольку <tex>c1</tex> содержит чётное число рёбер, инцидентных каждой вершине, обнаруженному жадным обходомто каждая вершина подграфа <tex>G'</tex> имеет чётную степень. Пусть <tex>e</tex> - ребро графа <tex>G'</tex>. Каждый разПоскольку <tex>G'</tex> имеет менее, чем <tex>n</tex> вершин, когда и у каждой вершины графа <tex>G'</tex> чётная степень, граф <tex>G'</tex> имеет эйлеров цикл. Пусть это цикл <tex>c2</tex>. У <tex>c1</tex> и <tex>c2</tex> имеется общая вершина этого цикла лежит также <tex>a</tex>, так как <tex>G</tex> cвязен. Теперь можно обойти эйлеров цикл, начиная его в <tex>а</tex>, обойти <tex>c1</tex> , вернуться в <tex>a</tex>, затем пройти <tex>c2</tex> и на другом цикле вернуться в одной из компонент связности<tex>a</tex>. Если новый эйлеров цикл не является эйлеровым циклом для <tex>G</tex>, обходим продолжаем использовать этот процесс, расширяя наш эйлеров цикл. Очевидно, полученный путь будет являться циклом и обходит все рёбра графапока, в конце концов, не получим эйлеров цикл для <tex>G</tex>.
}}
