Изменения

Без потери общности пусть <tex> v_x = v_n </tex>. Рассмотрим <tex> 2|E| = \sum_{i=1}^n deg(v_i) = \sum_{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> 2|E| \leqslant \sum_{i=1}^n deg(v_i) = \sum_{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>