112
правок
Изменения
Убрал теорему Schmeichel & Hakimi, добавил утверждение с теоремой Оре
[[Файл: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> C </tex>, можно считать хордами.
Пусть в графе нет цикла длины <tex> l </tex>, <tex> 3 \leqslant l \leqslant n-1 </tex> (по условию в графе существует гамильтонов цикл, длина которого равна <tex> n </tex>). Рассмотрим две соседние вершины <tex> v_i v_{i+1} </tex> и вместе с ними рассмотрим следующие пары:
}}
{{ТеоремаУтверждение|aboutid =Schmeichel & Hakimistatement|statement=<tex>G(V, E) , |V| = n , |E| = m, \forall (u, v) \notin E : deg(u) + deg(v) \geqslant n </tex>Тогда верно одно из двух утверждений:#<tex> G </tex> {{---}} гамильтонов панциклический граф#<tex> G </tex> = <tex>K_{n / 2, n / 2}</tex>|V| proof=По [https://neerc.ifmo.ru/wiki/index.php?title= %D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%9E%D1%80%D0%B5 теореме Оре] <tex> G </tex> - гамильтонов граф. Покажем, что <tex> m \geqslant n, v_1 v_2 v_3 ^2/4 </tex>. Пусть <tex> k </tex> - минимальная степень вершины в графе. # <tex> k \ldots v_n v_1 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>. Пусть существует x вершин, так что их степени равны <tex> k </tex>, тогда они все должна быть связаны, для которого выполняется неравенство так как иначе мы получим противоречие с утверждением теоремы <tex> \forall (u, v) \notin E : deg(v_1u) + deg(v_nv) \geqslant n </tex>. <br>Тогда Понятно, что <tex> G x \leqslant k + 1 </tex> {{---}} панциклический , но так как графявляется гамильтоновым, двудольный граф или графто он связен, в котором нет только цикла длины а значит <tex>(n-x < k + 1)</tex>...
<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>
Итоге граф подходит под условия теоремы.
}}
