Изменения
Нет описания правки
Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ge 3</tex> и <tex>\delta \ge n/2</tex>, то <tex>G</tex> - гамильтонов граф.
|proof=
Для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>, поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G</tex> - гамильтонов граф.
}}
==См. также==
* [[Гамильтоновы графы]]
* [[Теорема Хватала]]
== Источники ==
