Изменения

Пусть <tex>G</tex> {{---}} граф, в котором <tex>2N</tex> вершин имеют нечетную нечётную [[Основные определения теории графов|степень]]. Тогда множество ребер рёбер <tex>G</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> (критерием Эйлеровости графа является отсутствие нечетных нечётных вершин в связном мультиграфе).

Удалим из <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/>