Изменения

При <tex>k = < n</tex> доказано.Рассмотрим граф <tex>G = (V, E) </tex> в котором количество вершин с четной степенью больше нуля. Рассмотрим произвольную вершину <tex>u</tex>. Из нее выходит ребро. Пойдем по нему и будем действовать далее также. Таким образом можно дойти до <tex>u</tex> и найти цикл. Выкинем ребра цикла из графа. Первое условие сохранится. Второе может не выполниться, найдём эйлеров цикл в каждой получившейся компоненте связности. Восстановить эйлеров цикл исходного графа можно следующим образом: идём по первому циклу, обнаруженному жадным обходом. Каждый раз, когда вершина этого цикла лежит также и на другом цикле в одной из компонент связности, обходим этот цикл. Очевидно, полученный путь будет являться циклом и обходит все рёбра графа.