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

Эта статья находится в разработке!

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

Пусть [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][/math] По теореме Хватала: для [math]\forall k[/math] верна импликация [math]d_k \le k \lt n/2 \Rightarrow d_{n-k} \ge n-k[/math], поскольку левая её часть всегда ложна.

[math]\triangleleft[/math]

Источники

Харари Ф. - Теория графов. ISBN 978-5-397-00622-4