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