105
правок
Изменения
→Критерий Эйлеровости
Необходимость:
<br/>
Докажем утверждение по индукции.<br>''База'' - лес из <math>N</math> деревьев, каждое из 1 вершины.<br>''Переход:''<br>
Рассмотри граф, в котором степени всех вершин четные.<br/>
В нем найдется простой цикл, т.к. иначе граф является лесом <math>-></math> в нем есть хотя бы два листа, что противоречит четности степеней всех вершин.<br/>
