59
правок
Изменения
Нет описания правки
'''Необходимость'''<br/>
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями.<br/>
Добавим в <tex>G</tex> <tex> N </tex> ребер <tex>uv</tex> таких, что <tex>uv</tex> <tex>\notin</tex> <tex>G</tex> и степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в <tex>G</tex> появится Эйлеров цикл <tex>c</tex>. Удалим из <tex>c</tex> добавленные ребра.<br/>
Заметим, что теперь цикл распадается на <tex> N </tex> простых путей. В самом деле: отметим удаленные ребра в порядке их обхода в Эйлеровом цикле. Тогда <tex> c </tex> разбивается на <tex> N </tex> реберно-непересекающихся путей, т.к. каждый такой путь мы можем сопоставить удаленному ребру. Необходимость доказана.
