Изменения

[[Файл: Факторизация K7.png|thumb|360px|right{{Теорема|<tex>2</tex>-факторизация графа <tex>K_7</tex>. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной [[Укладка графа на плоскости|укладке графа]].]]statement =Если граф <tex>2</tex>-факторизуем, то каждый его фактор должен быть объединением непересекающихся (по вершинам) [[Основные определения теории графов|циклов]]. Если |proof =Начнём обход <tex>2</tex>-фактор связенфактора с какой-то вершины. Пойдём по одному из её рёбер и попадаем в смежную ей вершину. Далее идём по рёбрам, то он является [[Гамильтоновы графы|гамильтоновым циклом]]по которым мы ещё не ходили. Поскольку Мы входим в вершину по одному ребру и выходим по другому, так как степень каждой вершины равна <tex>2</tex>-факторизуемом графе все , пока не вернёмся в первую вершину. Это цикл, так как в каждой вершине мы были только один раз. Если есть вершины должны иметь чётные степени, которые мы не посетили, то полный граф <tex>K_{2nснова начинаем обход с любой из таких вершин. В вершины прежних циклов попасть нельзя, так как мы уже проходили по рёбрам этих вершин. Значит, циклы не пересекаются по вершинам.}}</tex> не является  Заметим, что если <tex>2</tex>-факторизуемым. Нечётные полные фактор связен, то он является [[Гамильтоновы графы <tex>2</tex>-факторизуемы|гамильтоновым циклом]].  

[[Файл: Факторизация K7.png|thumb|360px|right|<tex>2</tex>-факторизация графа <tex>K_7</tex>. Рёбра, отмеченные пунктиром, не пересекают другие рёбра при правильной [[Укладка графа на плоскости|укладке графа]].]]Для того чтобы в графе <tex>K_{2n+1}</tex> построить <tex>n</tex> гамильтоновых циклов, непересекающихся по рёбрам, перенумеруем сначала его вершины <tex>v_1, v_2, \dots, v_{2n+1}</tex>. На множестве вершин <tex>v_1, v_2, \dots, v_{2n}</tex> зададим <tex>n</tex> непересекающихся простых цепей <tex>P_i=v_i v_{i-1} v_{i+1} v_{i-2} \dots v_{i+n-1}v_{i-n}</tex> следующим образом: <tex>j</tex>-ой вершине цепи <tex>P_i</tex> является вершина <tex>v_k</tex>, где <tex>k=i+(-1)^{j+1}[j/2]</tex>, все индексы приводятся к числам <tex>1, 2, \dots, 2n </tex> по модулю <tex>2n</tex>. Гамильтонов цикл <tex>Z_i</tex> можно получить, соединив вершину <tex>v_{2n+1}</tex> с концевыми вершинами цепи <tex>P_i</tex>.