Пусть <tex>G</tex> {{---}} граф, в котором <tex>2N</tex> вершин имеют нечетную [[Основные определения теории графов|степень]]. Тогда множество ребер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|реберно-простыми]] путями.
|proof=
[[Файл:Make_edges_paths_1.png|180px|right|thumb|Пример графа для <tex>N = 2</tex>]]
[[Файл:Граф.jpg|180px|right|thumb|Пример доказательства на заданном графе <tex>N = 2</tex>]]
'''Необходимость'''
'''Необходимость'''<br/>Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями.<br/> Добавим <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> реберно-непересекающихся путей, т.к. каждый такой путь мы можем сопоставить удаленному ребру. Необходимость доказана.
Добавим <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> добавленные ребра.
Заметим, что теперь цикл распадается на <tex> N </tex> простых путей. В самом деле: возьмем Эйлеров цикл и удалим из него <tex>N</tex> ребер. Теперь полученный граф можно разбить на <tex>N</tex> (или меньше) цепей между этими удаленными ребрами.
'''Достаточность'''
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.
Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>. Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_m}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_m}u_{{i+1}_0}</tex> (соединяют конец предыдущей и начало следующей цепи) и ребро <tex>u_{k_m}u_{1_0}</tex> (соединяет конец последней и начало первой цепей).
В новом графе появится Эйлеров цикл, т.к. мы добавили ребра, соединяющие конец и начало <tex> i </tex> и <tex> i + 1 </tex> пути соответственно. Всего добавлено <tex>k</tex> ребер, которые меняют четность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</tex>, то в графе останутся вершины нечетной степени, что не удовлетворяет критерию Эйлеровости графа.<br/>
'''Достаточность'''<br/>
Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями.<br/>
Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, ... p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>.<br/>
Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}...u_{i_l}</tex>. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_l}u_{{i+1}_0}</tex> и ребро <tex>u_{k_l}u_{1_0}</tex>. В новом графе появится Эйлеров цикл, т.к. мы добавили ребра, соединяющие конец и начало <tex> i </tex> и <tex> i + 1 </tex> пути соответственно. Всего добавлено <tex>k</tex> ребер, которые меняют четность не более, чем <tex>2k</tex> вершин. Т.к. <tex>k < N</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>.
}}
