Как применяется теорема Эйлера для обхода графов без повторов?

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

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

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

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