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

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

Лемма (о длине цикла):

Пусть [math]G[/math] — произвольный неориентированный граф и [math]\delta[/math] — минимальная степень его вершин. Если [math]\delta \geqslant 2[/math], то в графе [math]G[/math] существует цикл [math]C[/math] длиной [math]l \geqslant \delta + 1[/math].

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

[math]\triangleright[/math]

Рассмотрим путь максимальной длины [math]P = v_0 v_1 \dots v_s[/math]. Все смежные с [math]v_0[/math] вершины лежат на [math]P[/math]. Обозначим [math]k = \max \{i: v_0 v_i \in E\} [/math]. Тогда [math]\delta \leqslant \deg v_0 \leqslant k[/math]. Цикл [math]C = v_0 v_1 \dots v_k v_0[/math] имеет длину [math]l = k + 1 \geqslant \delta + 1[/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]\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.