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

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

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

Пусть [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 \delta + 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]v \in C[/math] и расстояние от [math]v[/math] до [math]y[/math] по циклу меньше [math]m[/math]. Тогда этот участок цикла можно заменить на [math]v \rightarrow x \rightarrow P \rightarrow y[/math], длина которого [math]m + 1[/math]. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикла [math]C[/math]. Отсюда также следует, что [math]l \gt 2m[/math]. двум смежным вершинам на [math]C[/math]. Пусть [math]u, v \in C[/math] и [math]\{(u, v), (u, x), (x, v)\} \in E[/math]. Тогда заменив ребро [math](u, v)[/math] на [math]u \rightarrow x \rightarrow v[/math], увеличим длину цикла на [math]1[/math]. вершинам из [math]G \backslash (C \cup P)[/math], поскольку [math]P[/math] максимальный. Получаем [math]deg\ x \le m + (l - 2m)/2 =l/2 \lt n/2 \le \delta[/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]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math], поскольку левая её часть всегда ложна.

[math]\triangleleft[/math]

Источники

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