Изменения

Без потери общности пусть <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> 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>. Данное равенство достигается, если верно, что:

}}

<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) \geqslant n </tex>. <br>

Тогда <tex> G </tex> {{---}} панциклический граф, двудольный граф или граф, в котором нет только цикла длины <tex>(n-1)</tex>.

}}