59
правок
Изменения
Нет описания правки
|proof=
[[Файл:Make_edges_paths_1.png|180px|right|thumb|Пример графа для <tex>N = 2</tex>]]
[[Файл:Граф.jpg|180px|right|thumb|Пример доказательства на заданном графе <tex>N = 2</tex>]]
'''Необходимость'''<br/>
Противоречие. Значит, такого набора, что его мощность меньше <tex>N</tex>, не существует.
'''Пример на заданном графе'''<br/>
Добавим в наш граф ребра <tex> 2-5, 4-5 </tex> (для наглядности они помечены пунктиром). Заметим, что у нас есть эйлеров цикл: <tex>1-2-3-4-2-5-1-4-5</tex>. Удалим добавленные ребра и попытаемся пойти в порядке обхода, так мы получим 2 реберно-непересекающихся путей : <tex>1-2-3-4-2</tex> и <tex>5-1-4</tex>.
}}
