Изменения
Нет описания правки
|proof=
Пусть <tex>C</tex> - цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \ge \delta + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x..y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \ge n/2</tex>, а значит <tex>\delta \ge n - \delta > n - l = |V(G \backslash C)|</tex> и каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>.
Заметим, что вершина <tex>x</tex> не может быть смежна с вершинами из <tex>C</tex>, расстояние от которых до <tex>y</tex> (по <tex>C</tex>) не превышает m, а также двум смежным вершинам(это противоречило бы максимальности цикла <tex>C</tex>). Она также не может быть смежна с вершинами <tex>G \backslash (C \cup P)</tex>, поскольку <tex>P</tex> максимальный. Получаем <tex>deg\ x \le m + (l - 2m)/2 =l/2 < n/2 \le \delta</tex>. Противоречие.
}}
