Следующее утверждение являются следствием из [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|критерия Эйлеровости]] [[Основные определения теории графов|графа]]:
{{Теорема|statement=
Пусть <tex>G</tex> {{---}} связный граф, в котором <tex>2N</tex> вершин имеют нечетную нечётную [[Основные определения теории графов|степень]]. Тогда множество ребер рёбер <tex>G</tex> можно покрыть <tex>N</tex> [[Основные определения теории графов|ребернорёберно-простыми]] путями.
|proof=
'''Необходимость'''Рассмотрим граф <tex>G,</tex> который содержит <tex>2N</tex> вершин, имеющих нечётную степень. Докажем, что его можно покрыть <tex>N</tex> рёберно-простыми путями.
Докажем, что <tex>G</tex> можно покрыть <tex>N</tex> реберно-простыми путями. Добавим в граф <tex> N </tex> ребер <tex>uv</tex> такихрёбер, соединив попарно вершины, что имеющие нечётные степени вершин <tex>u</tex> и <tex>v</tex> нечетные. Тогда степени всех вершин станут четными, и в получим связный граф <tex>G',</tex> появится Эйлеров цикл <tex>c</tex> (критерием Эйлеровости графа является отсутствие нечетных вершин в связном мультиграфе)все вершины которого имеют чётную степень. Такой граф удовлетворяет [[Эйлеровость_графов#.D0.9A.D1.80.D0.B8.D1.82.D0.B5.D1.80.D0.B8.D0.B9_.D1.8D.D0.B9.D0. Удалим из <tex>c</tex> добавленные ребраBB.Заметим, что теперь цикл распадается на <tex> N </tex> простых путейD0. В самом деле: возьмем Эйлеров цикл и удалим из него <tex>N</tex> реберB5. Теперь полученный граф можно разбить на <tex>N</tex> (или меньше) цепей между этими удаленными ребрамиD1. '''Достаточность''' Докажем, что <tex>G</tex> нельзя покрыть менее, чем <tex>N</tex> реберно-простыми путями80. Предположим, что такое возможно, и существует набор реберно-простых путей <tex>p_1, p_2, D0.BE.D0. p_k, k < N</tex>, такой что он покрывает все ребра <tex>G</tex>B2. Пусть <tex>i-</tex>й путь из этого набора имеет вид <tex> w_i = u_{i_0}e_{i_1}u_{i_1}D0.BE.D1.u_{i_m}</tex>81. Добавим в <tex>G</tex> все ребра вида <tex>u_{i_m}u_{{i+1}_0}</tex> (соединяют конец предыдущей и начало следующей цепи) и ребро <tex>u_{k_m}u_{1_0}</tex> (соединяет конец последней и начало первой цепей)D1. В новом графе появится Эйлеров цикл, т82.кD0. мы добавили ребра, соединяющие конец B8|критерию эйлеровости]] и начало <tex> i </tex> содержит эйлеров цикл. Рассмотрим этот цикл и удалим из него <tex> i + 1 </tex> пути соответственно. Всего добавлено <tex>kN</tex> добавленных ребер, которые меняют четность не более, чем <tex>2kG' \backslash G.</tex> вершин. Т.к. Цикл распадётся на <tex>k < N</tex>путей, то в графе останутся вершины нечетной степеникоторые являются простыми, что не удовлетворяет критерию Эйлеровости графа.<br/> Противоречие. Значиттак как рассматриваемый цикл эйлеров, такого набораи покрывают весь граф, что его мощность меньше <tex>N</tex>, не существуетпоэтому полученное разбиение является искомым.
}}
==См. также==
* [[Эйлеров_цикл,_Эйлеров_путь,_Эйлеровы_графы,_Эйлеровость_орграфов|Эйлеров цикл, Эйлеров путь, Эйлеровы графы, Эйлеровость орграфовграфов]]
==Источники информации==
