Изменения
fixed 5 6 8 9 10 11
[[Файл:Circle 1.jpg|200px|left]] [[Файл: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) mod n + 1} </tex>.
Пусть в графе нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_i v_{i+1} </tex> и вместе с ними рассмотрим следующие пары:
Для <tex>k</tex> таких, что <tex> v_k </tex> лежит на дуге <tex> (v_{j + l - 1 \leqslant k \leqslant }, v_{j + l }, v_{j - 2 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 \leqslant k \leqslant }, 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{}{}{}{}{n-1}{2} </tex>.
Пусть это не так, тогда <tex> \forall i, 1 \leqslant i \leqslant n : deg(i) \geqslant \genfrac{}{}{}{}{n-1}{2} + 1 = \genfrac{}{}{}{}{n+1}{2} </tex>, значит <tex> \forall j, 1 \leqslant j \leqslant n : deg(v_j) + deg(v_{j+1}) \geqslant \genfrac{}{}{}{}{n+1}{2} + \genfrac{}{}{}{}{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\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{(n - 1)/2} (deg(v_{2i-1}) + deg(v_{2i})) + deg(v_n) \leqslant \genfrac{}{}{}{}{n(n-1)}{2} + \genfrac{}{}{}{}{n-1}{2} < </tex> <tex> \genfrac{}{}{}{}{n^2}{2} </tex>, то есть <tex> |E| < \genfrac{}{}{}{}{n^2}{24} </tex>, но по условию <tex> |E| \geqslant n^2/4 </tex> {{--- }} получили противоречие. Таким образом <tex> n </tex> является четным. Тогда верно, что <tex> 2|E| \leqslant \sum\limits_{i=1}^n deg(v_i) = \sum\limits_{i=1}^{n/2} (deg(v_{2i-1}) + deg(v_{2i})) \leqslant \genfrac{}{}{}{}{n^2}{2} </tex>, а так как по условию <tex> |E| \geqslant n^2/4 </tex>, то <tex> |E| = \genfrac{}{}{}{}{n^2}{4} </tex>. Данное равенство достигается, если верно, что:
[[Файл:Circle 3.jpg|800px|right]]
Пусть <tex> G </tex> не <tex> K_{n/2, n/2} </tex>, тогда существует такое четное число <tex> k </tex>, что в графе <tex> G </tex> существует ребро <tex> (v_j, v_{j+k}) </tex>. Докажем, что в таком случае существует ребро <tex> (v_j, v_{j+2}) \in E </tex>. Пусть это не так и минимальное четное <tex> k </tex>, что <tex> \exists (v_j, v_{j+k}) \in E </tex> больше двух, т.е. <tex> k \geqslant 4 </tex>. Тогда существует три случая:
# <tex> 4 \leqslant k \leqslant n - l </tex> <br> <tex> (v_j, v_{j+k}) \in E \Rightarrow (v_{j+1}, v_{j+k+l-3}) \notin E \Rightarrow (v_{j+2}, v_{j+k}) \in E </tex> <br> <tex> \exists l = k-2 : (v_i, v_{i+l}) \in E </tex> {{- --}} противоречие с минимальностью <tex> k </tex># <tex> n - l + 2 \leqslant k \leqslant 2n - 2l </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-4}) \in E </tex> <br> однако <tex> 2n - k - 2l + 2 \leqslant k - 2 </tex> {{--- }} противоречие с минимальностью <tex> k </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> G </tex> существует ребро <tex> (v_j, v_{j+2}) </tex>, но тогда <tex> (v_j, v_{j+l}) \notin E </tex>, а следовательно <tex> (v_{j+1}, v_{j+3}) \in E </tex>. Если продолжить по всему графу, то получим, что <tex> \forall j : (v_j, v_{j+2}) \in E </tex> и, как следствие, <tex> G </tex> {{- --}} панциклический.
}}
#<tex> G </tex> {{---}} панциклический граф
#<tex> G </tex> = <tex>K_{n / 2, n / 2}</tex>
|proof=По [[Теорема Оре|теореме Оре]] <tex> G </tex> {{- --}} гамильтонов граф. Покажем, что <tex> m \geqslant n^2/4 </tex>. Пусть <tex> k </tex> {{--- }} минимальная степень вершины в графе. # <tex> k \geqslant n/2 </tex>, тогда <tex> 2m = \sum\limits_{i=1}^n deg(v_i) >= \sum\limits_{i=1}^n k = k * n \geqslant n^2/2 </tex> # <tex> k < 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> n - k - 1 </tex> стпени степени которых как минимум <tex> n - k </tex>. Тогда можно оценить количество ребер. <br> <tex> m \geqslant \genfrac{}{}{}{}{1}{2}((n-k-1)(n-k)+k^2+k+1) = \genfrac{}{}{}{}{1}{2}(n^2 - n(2k + 1) + 2k^2 + 2k + 1) \geqslant \genfrac{}{}{}{}{n^2+1}{4} </tex>
Итого граф подходит под условия теоремы.
