210
правок
Изменения
м
|proof =
Возьмем две любые несмежные вершины <tex> u </tex> и <tex> v </tex>. Пусть <tex> \deg u = k </tex>. Тогда <tex> \deg v \geqslant n - k </tex>. Возьмем <tex> k </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> {{---}} гамильтонов граф.
Нет описания правки
|statement =
Если <tex> n \geqslant 3 </tex> и <tex> \deg u + \deg v \geqslant n </tex> для любой пары <tex> u </tex> и <tex> v </tex> несмежных вершин графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
}}
|statement =
Если <tex> n > 3 </tex> и <tex> \deg v \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </tex> {{---}} гамильтонов граф.
}}
