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

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

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Теорема (Дирак):

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

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

[math]\triangleright[/math]

Пусть [math]C[/math] - цикл наибольшей длины в графе [math]G[/math]. По лемме его длина [math]l \ge n + 1[/math]. Если [math]C[/math] - гамильтонов, то теорема доказана. Предположим обратное, т. е. [math]G \backslash C \ne \varnothing[/math]. Рассмотрим путь [math]P = x..y : P \cap C = \{y\}[/math] наибольшей длины [math]m[/math]. Заметим, что по условию [math]\delta \ge n/2[/math], а значит [math]\delta \ge n - \delta \gt n - l = |V(G \backslash C)|[/math] и каждая вершина из [math]G \backslash C[/math] смежна с некоторыми вершинами из [math]C[/math]. Заметим, что вершина [math]x[/math] не может быть смежна с вершинами из [math]C[/math], расстояние от которых до [math]y[/math] (по [math]C[/math]) не превышает m, а также двум смежным вершинам(это противоречило бы максимальности цикла [math]C[/math]). Получаем [math]deg\ x \le m + (l - 2m)/2 =l/2 \lt n/2 \le \delta[/math]. Противоречие.

[math]\triangleleft[/math]

Обратим внимание, что эта теорема является следствием из теоремы Хватала. Действительно, для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math], поскольку левая её часть всегда ложна.

Источники

Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1