|
proof=
'''Достаточность:'''
Рассмотрим эйлеров цикл <tex>p</tex> в <tex>G</tex>.
Каждое вхождение вершины в цикл(кроме первого и последнего вхождения начальной вершины) добавляет 2 к ее степени.<br/>
Для начальной вершины ее первое и последнее вхождение также суммарно добавляют 2 к ее степени. В итоге, каждая вершина имеет четную степень.
'''Необходимость:'''
Докажем утверждение по индукции.
''База:'' <br>
Лес из <tex>N</tex> деревьев, каждое из 1 вершины.
''Переход:''<br>
Рассмотри граф, в котором степени всех вершин четные.
В нем найдется простой цикл, т.к. иначе граф является [[Дерево, эквивалентные определения|лесом]], и тогда в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.
Рассмотрим цикл <tex>c</tex> такой, что при удалении его ребер не образуется двух компонент связности размера больше 1.
Такой всегда существует, т.к. [[Граф_блоков-точек_сочленения|граф блоков и точек сочленения]] произвольного почти связного графа является [[Дерево, эквивалентные определения|деревом]], а т.к. все вершины <tex>G</tex> имеют четные степени, то не могут являться в нем листами. Значит, листами в дереве блоков и точек сочленения такого графа будут циклы, а в любом цикле есть подмножество, являющееся простым циклом.
Рассмотрим вершину <tex>u</tex> со степенью больше 2. После удаления цикла <tex>c</tex> из графа степени всех вершин останутся четными,
при этом количество ребер в графе уменьшится. Для <tex>G - c</tex>, по предположению индукции, существует эйлеров цикл <tex>e</tex>.
Тогда в <tex>G</tex> тоже существует эйлеров обход - сначала обойти цикл <tex>c</tex>, начиная с вершины <tex>u</tex>, затем обойти <tex>e</tex>.
Переход доказан.
}}
'''Следствие'''
