Изменения

[[Файл:Circle 1.jpg|200px|left|thumb| Синим цветом выделен гамильтонов цикл<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>) выделены. Дугии ребра, окрашенный окрашенные в зеленый цвет, образуют цикл длины l]] [[Файл:Circle 2.jpg|200px|right|thumb| Синим цветом выделен гамильтонов цикл<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>) выделены. Дугии ребра, окрашенный окрашенные в зеленый цвет, образуют цикл длины l]]

Пусть граф не панциклический, тогда в графе неи нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_j v_{j+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> 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> len((v_{k - l + 3}, v_{k - l + 4}, v_{k})) + 3 = k - (k - l + 3) + 3 = l - 3 + 3 = l </tex>.

Докажем методом от противного{{Лемма|statement=Если для графа <tex> G </tex> выполнены условия из теоремы и в нем отсутствует цикл длины <tex> l </tex>, что <tex> 3 \leqslant l \leqslant n -1 </tex> {{---}} четно, то количество вершин в графе четное|proof= Доказательство будем вести методом от противного. *Пусть <tex> n </tex> является нечетным, тогда из рассуждений выше существует вершина <tex> v_x </tex>, для которое верно, что <tex> deg(v_x) \leqslant \genfrac{}{}{}{0}{n-1}{2} </tex>. **Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(v_i) \geqslant \genfrac{}{}{}{0}{n-1}{2} + 1 = \genfrac{}{}{}{0}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{0}{n+1}{2} + \genfrac{}{}{}{0}{n+1}{2} = n + 1 </tex>, то есть мы получили противоречие с тем, что <tex> deg(v_j) + deg(v_{j + 1}) \leqslant n </tex>.*Без потери общности пусть <tex> v_x = v_n </tex>. Рассмотрим <tex> 2|E| = \sum_sum\limits_{i=1}^n deg(v_i) = \sum_sum\limits_{i=1}^{\genfrac{}{}{}{}{n - 1}{2}} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{0}{n(n-1)}{2} + </tex> <tex> \genfrac{}{}{}{0}{n-1}{2} < \genfrac{}{}{}{0}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{0}{n^2}{4} </tex>, но по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex> {{---}} получили противоречие. Таким образом }}  По лемме <tex> n </tex> является четным, если в цикле отсутствует цикл длины <tex> l </tex>. Тогда верно, что <tex> 2|E| = \leqslant sum\sum_limits_{i=1}^n deg(v_i) = \sum_sum\limits_{i=1}^{\genfrac{}{}{}{}{n}{2}} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{0}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant \genfrac{}{}{}{0}{n^2}{4} </tex>, то <tex> |E| = \genfrac{}{}{}{0}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:

*<tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1}, v_{j + l}, v_{j - 1}) </tex>: <tex> (v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \notin E </tex> или <tex> (v_j, v_k) \notin E </tex> и <tex>(v_{j+1}, v_{k-l+3}) \in E </tex>

*<tex> v_k </tex> лежит на дуге <tex> (v_{j + 2}, v_{j + 3}, v_{j + l - 2}) </tex>: <tex>(v_j, v_k) \in E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \notin E </tex> или <tex>(v_j, v_k) \notin E </tex> и <tex>(v_{j+1}, v_{k-l+1}) \in E </tex>

# <tex> 2n - 2l + 2 \leqslant k \leqslant n - 2 </tex> <br> <tex> (v_j, v_{j+k}) \in E \Rightarrow (v_{j-1}, v_{j+k+l-1}) \notin E \Rightarrow (v_{j-2}, v_{j+k+2l-2}) \in E </tex> <br> однако <tex> k + 2l - 2n \leqslant k - 2 </tex> {{---}} снова проиворечие противоречие с минимальностью выбранного k

# <tex> k \geqslant \genfrac{}{}{}{0}{n}{2} </tex>, тогда <tex> 2m = \sum_sum\limits_{i=1}^n deg(v_i) >= \sum_sum\limits_{i=1}^n k = k n \geqslant \genfrac{}{}{}{0}{n^2}{2} </tex> # <tex> k < \genfrac{}{}{}{0}{n}{2} </tex>. Пусть существует <tex> x </tex> вершин, так что их степени равны <tex> k </tex>, тогда они все должны быть связаны, так как иначе мы получим противоречие с утверждением теоремы <tex> \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>. Понятно, что <tex> x \leqslant k + 1 </tex>, но так как граф является гамильтоновым, то он связен, а значит <tex> x < k + 1 </tex>. Несложно заметить, что если из всех <tex> x </tex> вершин степени <tex> k </tex> провести оставшиеся ребра в одну вершину, у которой степень больше, то в графе остенется как минимум <tex> n - k - 1 </tex> вершин, степени которых как минимум <tex> n - k </tex>, поскольку должно выполняться неравенство из теоермы. Тогда можно оценить количество ребер. <br> <tex> m \geqslant \genfrac{}{}{}{0}{1}{2}((n-k-1)(n-k)+k^2+(k+1)) = \genfrac{}{}{}{0}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{0}{n^2+1}{4} </tex>