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

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

Доказательство: если взять эйлеров цикл и ориентировать все его рёбра в порядке обхода, то из каждой вершины будет выходить столько же рёбер, сколько входить. 3 Значит, степень у всех вершин исходного неориентированного графа была чётной. 3

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