Изменения

''База'' - лес из <math>N</math/> деревьев, каждое из 1 вершины.

В нем найдется простой цикл, т.к. иначе граф является лесом <math>-></math> в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.<br/>Рассмотрим цикл <math>c</math/> такой, что при удалении его ребер не образуется компонент связности размера больше 1.<br/>Такой всегда существует, т.к. граф компонент двусвязности произвольного связного графа является деревом, а т.к. все вершины <math>G<math/>БРассмотрим вершину <math>u<math/> со степенью больше 2. После удаления цикла <math>c<math/> из графа степени всех вершин останутся четными,<br/> при этом количество ребер в графе уменьшится. Для <math>G - c<math/>, по предположению индукции, существует эйлеров цикл <math>e<math/>.<br/>Тогда в <math>G<math/> тоже существует Эйлеров обход - сначала обойти <math>с<math/>, начиная с <math>u<math/>, затем обойти <math>e<math/>.