Изменения
Нет описания правки
}}
{{Теорема
|proof=
[[Файл:Circle 1.jpg|200px|left||asdasdasdasd ad asdasd]] [[Файл:Circle 2.jpg|200px|right]]
Обозначим как <tex> C=v_1 v_2 v_3 \ldots v_n </tex> гамильтонов цикл в графе <tex> G </tex>. Для простоты расположим <tex> C </tex> на окружности. Также подразумевается, что все индексы при вершинах берутся по модулю, то есть <tex> v_j = v_{((j - 1)\bmod n) + 1} </tex>.
Пусть в графе нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_i v_j v_{ij+1} </tex> и вместе с ними рассмотрим следующие пары:
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j -1}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+3}</tex>) (см. рисунок слева)
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<tex>v_{j+1}, v_{k-l+1}</tex>) (см. рисунок справа)
При добавлении таких пар ребер в графе появляется цикл длины <tex> l </tex>(выделены зеленым цветом на рисунках слева и справа), а значить в <tex> G </tex> может входить максимум одно ребро из таких пар. Тогда можно утверждать, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.
Докажем методом от противного, что <tex> n </tex> {{---}} четно. Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>.
