Изменения

Пусть в графе нет цикла длины <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> j + l - 1 \leqslant k \leqslant j + l - 2 </tex> рассмотрим пары (<tex>v_j, v_k</tex>) и (<brtex>v_{j+1}, v_{k-l+3}</tex>) Для <tex>k</tex> таких, что <tex> j + 2 \leqslant k \leqslant 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}{2} </tex>, но по условию <tex> |E| \geqslant n^2/4 </tex> - получили противоречие. Таким образом <tex> n </tex> является четным.   

<tex>G = <V, E> </tex> {{---}} гамильтонов граф, <tex>|V| = n, v_1 v_2 v_3 \ldots v_n v_1 </tex> {{---}} его гамильтонов цикл, для которого выполняется неравенство <tex> deg(v_1) + deg(v_n) \geq geqslant n </tex>. <br>