Доказательство

Доказательство состоит из двух частей.

Необходимость Требуется доказать, что в любом эйлеровом графе степени всех вершин – чётные.

Пусть по некоторой вершине v цикл проходит k раз. Но так как перед этой вершиной и после неё цикл должен проходить по инцидентным ей рёбрам, то количество рёбер, инцидентных данной вершине, по которым проходит цикл – 2 k. Так как цикл эйлеров – рёбер, по которым цикл не проходит нет. Значит 2 k – степень вершины v.

Достаточность Требуется доказать, что если в связном графе степени всех вершин – чётные, то в графе существует эйлеров цикл. В ходе доказательства мы дадим алгоритм построения такого цикла.

Начнём с произвольной вершины v и будем строить из неё цепь, пока есть возможность её продолжить. Пусть в какой-то момент построения мы находимся в вершине u (не совпадающей с v). Тогда цепь, которую мы построили, проходит по нечётному числу рёбер, инцидентных данной вершине. Степень вершины u чётная, следовательно, есть хотя бы одно ребро, инцидентное вершине u, по которому цепь не прошла – значит её можно продолжить. Следовательно, цепь может закончится только в вершине v. Получим цикл.

Если данный цикл прошёл не по всем рёбрам графа, то ``разорвём'' цикл в вершине w, где к нему примыкает не пройденное ребро^* и будем двигаться дальше по новым рёбрам. Рассуждая также как и выше (относительно вершины v), заключаем, что мы обязательно вернёмся в вершину w. Далее к маршруту присоединяем свободный конец разорванного маршрута – снова получим цикл. Присоединяя таким образом одно ребро за другим, мы и получим эйлеров цикл.