Теорема Поша

Теорема

Теорема (Поша):

Пусть граф [math] G [/math] имеет [math]n \geqslant 3[/math] вершин и выполнены следующие два условия: [math] \forall [/math] [math]k,\, 1 \leqslant k \lt (n-1)/2[/math], число вершин со степенями, не превосходящими [math]k[/math], меньше чем [math]k[/math] для нечетного [math]n[/math] число вершин степени [math](n-1)/2[/math] не превосходит [math](n-1)/2[/math] тогда [math] G [/math] — гамильтонов граф.

Доказательство:

[math]\triangleright[/math]

Гамильтонов цикл [math] v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} [/math] Предположим, что теорема неверна. Пусть [math] G [/math] — максимальный негамильтонов граф с [math] n [/math] вершинами, удовлетворяющий условиям теоремы. Легко видеть, что добавление любого ребра в граф, обладающий указанными свойствами, приводит к графу, который также обладает этими свойствами. Таким образом, поскольку добавление к [math] G [/math] произвольного ребра приводит к гамильтонову графу, любые две несмежные вершины соединимы простым гамильтоновым путем. Покажем сначала, что всякая вершина, степень которой не меньше [math] (n-1)/2 [/math], смежна с каждой вершиной со степенью, большей чем [math] (n-1)/2 [/math]. Не умаляя общности, допустим, что [math] \deg v_{1} \geqslant (n-1)/2 [/math] и [math] \deg v_{n} \geqslant n/2 [/math], но вершины [math] v_{1} [/math] и [math] v_{n} [/math] не смежны. Тогда существует простой гамильтонов путь [math] v_{1} v_{2} \dotsc v_{n} [/math], соединяющий [math] v_{1} [/math] и [math] v_{n} [/math]. Обозначим вершины, смежные с [math] v_{1} [/math], через [math] v_{{i}_{1}}, \dotsc,v_{{i}_{k}} [/math], где [math] k = \deg v_{1} [/math] и [math] 2=i_{1} \lt i_{2} \lt \dotsc \lt i_{k} [/math]. Ясно, что вершина [math] v_{n} [/math] не может быть смежной ни с одной вершиной из [math] G [/math] вида [math] v_{{i}_{j-1}} [/math], поскольку тогда в [math] G [/math] был бы гамильтонов цикл [math] v_{1} v_{2} \dotsc v_{{i}_{j-1}} v_{n} v_{n-1} \dotsc v_{{i}_{j}} v_{1} [/math]. Далее, так как [math] k \geqslant (n-1)/2 [/math], то [math] n/2 \leqslant \deg v_{n} \leqslant n-1-k \lt n/2 [/math], что невозможно. Поэтому [math] v_{1} [/math] и [math] v_{n} [/math] должны быть смежны. Отсюда следует, что если [math] \deg v \geqslant n/2 [/math] для всех вершин [math] v [/math], то [math] G [/math] — гамильтонов граф. В силу изложенного выше каждая пара вершин графа [math] G [/math] смежна, т.е. [math] G [/math] — полный граф. Мы пришли к противоречию, поскольку [math] K_{n} [/math] — гамильтонов граф для всех [math] n \geqslant 3 [/math]. Таким образом, в [math] G [/math] есть вершина [math] v [/math] с [math] \deg v \lt n/2 [/math]. Обозначим через [math] m [/math] наибольшую среди степеней всех таких вершин. Выберем такую вершину [math] v_{1} [/math], что [math] \deg v_{1} = m [/math]. По принятому предположению число вершин со степенями, не превосходящими [math] m [/math], не больше чем [math] m \lt n/2 [/math], поэтому должно быть более чем [math] m [/math] вершин со степенями, превосходящими [math] m [/math], и, следовательно, не меньшими чем [math] n/2 [/math]. В результате найдется некоторая вершина, скажем [math] v_{n} [/math], степени по крайней мере [math] n/2 [/math], не смежная с [math] v_{1} [/math]. Так как [math] v_{1} [/math] и [math] v_{n} [/math] не смежны, то существует простой гамильтонов путь [math] v_{1} \dotsc v_{n} [/math]. Как и выше, обозначим через [math] v_{{i}_{1}}, \dotsc, v_{{i}_{m}} [/math] вершины графа [math] G [/math], смежные с [math] v_{1} [/math], и заметим, что вершина [math] v_{n} [/math] не может быть смежной ни с одной из [math] m [/math] вершин [math] v_{{i}_{j-1}} [/math] для [math] 1 \leqslant j \leqslant m [/math]. Но поскольку [math] v_{1} [/math] и [math] v_{n} [/math] не смежны, а [math] v_{n} [/math] имеет степень не меньше [math] n/2 [/math], то, как было показано в первой части доказательства, [math] m [/math] должно быть меньше чем [math] (n-1)/2 [/math]. Так как по предположению число вершин со степенями, не превосходящими [math] m [/math], меньше чем [math] m [/math], то хотя бы одна из [math] m [/math] вершин [math] v_{{i}_{j-1}} [/math], скажем [math] v' [/math], должна иметь степень не меньше [math] n/2 [/math]. Итак, мы установили, что степени двух несмежных вершин [math] v_{n} [/math] и [math] v' [/math] не меньше [math] n/2 [/math]. Полученное противоречие завершает доказательство теоремы.

[math]\triangleleft[/math]

Замечания

Кубический гамильтонов граф

• Приведенное достаточное условие не является необходимым. Изображенный на рисунке кубический граф — гамильтонов, хотя ясно, что он не удовлетворяет условиям теоремы.
• Условия теоремы нельзя улучшить, так как при их ослаблении новое условие уже не будет достаточным для гамильтоновости графа.

Следствия

Ограничивая условия теоремы Поша, получаем более простые, но менее сильные достаточные условия, найденные Оре и Дираком соответственно:

Теорема (Следствие 1):

Если [math] n \geqslant 3 [/math] и [math] \deg u + \deg v \geqslant n [/math] для любой пары [math] u [/math] и [math] v [/math] несмежных вершин графа [math] G [/math], то [math] G [/math] — гамильтонов граф.

Доказательство:

[math]\triangleright[/math]

Возьмем две любые несмежные вершины [math] u [/math] и [math] v [/math]. Пусть [math] \deg u = k [/math]. Тогда [math] \deg v \geqslant n - k [/math]. Возьмем [math] k [/math] как в условии теоремы Поша. Тогда, учитывая ограничения теоремы и что вершины несмежны, получаем, что следствие верно.

[math]\triangleleft[/math]

Теорема (Следствие 2):

Если [math] n \gt 3 [/math] и [math] \deg v \geqslant n/2 [/math] для любой вершины [math] v [/math] графа [math] G [/math], то [math] G [/math] — гамильтонов граф.

Доказательство:

[math]\triangleright[/math]

Возьмем любые несмежные вершины [math] u, v \in G [/math]. Тогда [math] \displaystyle \deg u + \deg v \geqslant \frac n 2 + \frac n 2 = n [/math]. По теореме Оре [math] G [/math] — гамильтонов граф.

[math]\triangleleft[/math]

См. также

• Теорема Оре
• Теорема Дирака
• Теорема Хватала
• Теорема Гринберга
• Теорема Редеи-Камиона

Источники информации

• Харари Ф. Теория графов: Пер. с англ. / Предисл. В. П. Козырева; Под ред. Г.П.Гаврилова. Изд. 4-е. — М.: Книжный дом "ЛИБРОКОМ", 2009. — 60 с.