Изменения
Нет описания правки
== Основные определения ==
{{Определение
|definition='''Панциклический граф''' (англ. ''pancyclic graph'') {{---}} граф, в котором есть циклы всех длин от <tex> 3 </tex> до <tex> n </tex>. Если граф содержит все циклы от <tex> r </tex> до <tex> n </tex>, то такой граф называют <tex> r </tex>-панциклическим.
}}
{{Определение
|definition='''<tex> r </tex>-панциклический граф''' (англ. ''<tex> r </tex>-pancyclic graph'') {{---}} граф содержит все циклы от <tex> r </tex> до <tex> n </tex>.
}}
== Предпосылка ==
{{Теорема
|about=Mantel
}}
== Основная теорема ==
{{Теорема
|about=J. A. Bondy
|proof=
[[Файл:Circle 1.jpg|200px|left|thumb| Синим цветом выделен гамилтонов гамильтонов цикл. Дуги, окрашенный в зеленый цвет, образуют цикл длины l]] [[Файл:Circle 2.jpg|200px|right|thumb| Синим цветом выделен гамилтонов гамильтонов цикл. Дуги, окрашенный в зеленый цвет, образуют цикл длины l]]
Обозначим как <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>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>.
}}
=== Следствие ===
{{Утверждение
|id = statement
