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