Теорема Дирака

Лемма о длине цикла

9М ТОП ОСТАЛЬНЫМ ПО ЕБАЛУ ХЛОП

Альтернативное доказательство

Теорема (Дирак — альтернативное доказательство):

Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/math], то [math]G[/math] — гамильтонов граф.

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

[math]\triangleright[/math]

Для [math]\forall k[/math] верна импликация [math]d_k \leqslant k \lt n/2 \Rightarrow d_{n-k} \geqslant n-k[/math], поскольку левая её часть всегда ложна. Тогда по теореме Хватала [math]G[/math] — гамильтонов граф.

[math]\triangleleft[/math]

Теорема (Вывод из теоремы Оре):

Пусть [math]G[/math] — неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]n \geqslant 3[/math] и [math]\delta \geqslant n/2[/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]

См. также

• Гамильтоновы графы
• Теорема Хватала
• Теорема Оре
• Теорема Поша

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

• Wikipedia — Dirac's Theorem
• Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.