54
правки
Изменения
Нет описания правки
{{Теорема
|statement=
Если <tex>\ n > 3</tex> и <tex>deg\ v \ge n/2</tex> для любой вершины <tex>\ v</tex> неориентированного графа <tex>\ G</tex>, то <tex>\ G</tex> - гамильтонов граф.
|proof=
По [[Теорема Хватала|теореме Хватала]]: для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>
}}
