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