210
правок
Изменения
м
Нет описания правки
|statement = Пусть граф <tex> G </tex> имеет <tex>n \geqslant 3</tex> вершин и выполнены следующие два условия:
*для всякого <tex> \forall </tex> <tex>k,\, 1 \leqslant k < (n-1)/2</tex>, число вершин со степенями, не превосходящими <tex>k</tex>, меньше чем <tex>k</tex>;*для нечетного <tex>n</tex> число вершин степени <tex>(n-1)/2</tex> не превосходит <tex>(n-1)/2</tex>,
тогда <tex> G </tex> {{---}} [[Гамильтоновы графы|гамильтонов]] граф.
|proof =
[[Файл: Graph-Posha.png|500px|thumb|right|Гамильтонов цикл <tex> v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} </tex>]]
Предположим, что теорема неверна. Пусть <tex> G </tex> {{---}} максимальный негамильтонов граф с <tex> n </tex> вершинами, удовлетворяющий условиям теоремы.
==Замечания==
[[Файл: Graph-Posha-Cubic.png|250px|thumb|right|Кубический гамильтонов граф]]
*Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф {{---}} гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
*Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.
Если <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> u </tex> и <tex> v </tex>. Пусть <tex> \deg u = k </tex>. Тогда <tex> \deg v \geqslant n - k </tex>. Возьмем <tex> k </tex> как в теореме условии теоремы Поша. Тогда, учитывая ограничения теоремы и что вершины не смежнынесмежны, получаем, что следствие верно.
}}
Если <tex> n > 3 </tex> и <tex> \deg v \geqslant n/2 </tex> для любой вершины <tex> v </tex> графа <tex> G </tex>, то <tex> G </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> {{---}} гамильтонов граф.
}}
