Изменения
Нет описания правки
Для <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>. *Рассмотрим второй слуйчайслучай, когда <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> len((v_{k}, v_{k - 1}, v_{k - l + 1})) - 1 + 2 = k - (k - l + 1) - 1 + 2 = l - 1 - 1 + 2 = 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{}{}{}{0}{n-1}{2} </tex>.
