Бюрократы, editor, Администраторы
422
правки
Изменения
пояснение
Если <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> , поскольку левая её часть всегда ложна.
}}
== Источники ==
Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''
