Доказательство. Пусть связной граф является Эйлеровым, тогда существует циклический Эйлеров путь

Необходимость.

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

Достаточность.

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

1 случай: все ребра окрашены.

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

Пусть у степень четная, тогда путь может закончиться в вершине .

, где – некоторая цепь. Получили другой циклический путь.

Если остались еще неокрашенные ребра, то продолжаем процедуру. Получаем Эйлеров путь.