Изменения

Если Пусть <tex>n > 3G</tex> {{---}} неориентированный граф и <tex>deg\ v \ge n/2delta</tex> для любой вершины {{---}} минимальная степень его вершин. Если <tex>vn \geqslant 3</tex> неориентированного графа и <tex>G\delta \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> {{---}} гамильтонов граф.

==См. также==* [[Гамильтоновы графы]]* [[Теорема Хватала]]* [[Теорема Оре]]* [[Теорема Поша]] == Источники информации ==Харари Ф* [[wikipedia:en:Dirac's_Theorem|Wikipedia {{---}} Dirac's Theorem]]* Graham, R.L., Groetschel M., and Lovász L. - Теория графов, eds. (1996). ''Handbook of Combinatorics'', Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 9780-5262-39707169-00622-4'''X.  [[Категория: Алгоритмы и структуры данных]][[Категория: Обходы графов]][[Категория: Гамильтоновы графы]]