Изменения

Добавим <tex> N </tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> <tex>\notin</tex> <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex> (критерием Эйлеровости графа является отсутствие нечетных вершин в связном мультиграфе).