Изменения

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