Изменения

|statement= Пусть <tex>G</tex> {{- --}} произвольный неориентированный граф и <tex>\delta</tex> {{--- }} минимальная степень его вершин. Если <tex>\delta \ge geqslant 2</tex>, то в графе <tex>G</tex> существует цикл <tex>C</tex> длиной <tex>l \ge geqslant \delta + 1</tex>.

Рассмотрим путь максимальной длины <tex>P = v_0 v_1 .. \dots v_s</tex>. Все смежные с <tex>v_0</tex> вершины лежат на <tex>P</tex>. Обозначим <tex>k = \max\{i: v_0 v_i \in E\}</tex>. Тогда <tex>\delta \le leqslant \deg\ v_0 \le leqslant k</tex>. Цикл <tex>C = v_0 v_1 .. \dots v_k v_0</tex> имеет длину <tex>l = k + 1 \ge geqslant \delta + 1</tex>

Пусть <tex>G</tex> {{- --}} неориентированный граф и <tex>\delta</tex> {{--- }} минимальная степень его вершин. Если <tex>n \ge geqslant 3</tex> и <tex>\delta \ge geqslant n/2</tex>, то <tex>G</tex> {{--- }} [[Гамильтоновы графы|гамильтонов граф]].

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

Получаем <tex>deg\ x \le leqslant m + (l - 2m)/2 =l/2 < n/2 \le leqslant \delta</tex>. Противоречие.

Пусть <tex>G</tex> {{- --}} неориентированный граф и <tex>\delta</tex> {{--- }} минимальная степень его вершин. Если <tex>n \ge geqslant 3</tex> и <tex>\delta \ge geqslant n/2</tex>, то <tex>G</tex> {{--- }} [[Гамильтоновы графы|гамильтонов граф]].

Для <tex>\forall k</tex> верна импликация <tex>d_k \le leqslant k < n/2 \Rightarrow d_{n-k} \ge geqslant n-k</tex>, поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G</tex> {{---}} гамильтонов граф.}} {{Теорема|about = Вывод из [[Теорема Оре|теоремы Оре]]|statement = Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то <tex>G</tex> {{- --}} [[Гамильтоновы графы|гамильтонов граф]].|proof = Возьмем любые неравные вершины <tex> u, v \in G </tex>. Тогда <tex> \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n </tex>. По теореме Оре <tex> G </tex> {{---}} гамильтонов граф.

* Graham, R.L., Groetschel M., and Lovász L., eds. (1996). ''Handbook of Combinatorics'', Volumes 1and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.* [[wikipedia:en:Dirac's_Theorem|Wikipedia {{---}} Dirac's Theorem]]