105
правок
Изменения
→Критерий Эйлеровости
<br/>
Докажем утверждение по индукции.<br>
''База:'' - лес <br/> Лес из <math>N</math> деревьев, каждое из 1 вершины.<br>
''Переход:''<br>
Рассмотри граф, в котором степени всех вершин четные.<br/>
при этом количество ребер в графе уменьшится. Для <math>G - c</math>, по предположению индукции, существует эйлеров цикл <math>e</math>.<br/>
Тогда в <math>G</math> тоже существует Эйлеров обход - сначала обойти цикл с, начиная с вершины <math>u</math>, затем обойти <math>e</math>.<br/>
|corollary=
Неориентированный связный граф <math>G = (V, E)</math> является полуэйлеровым тогда и только тогда, когда содержит ровно две вершины нечетной степени.<br/>
}}
====Ориентированный граф====
'''Теорема'''<br/>
