Изменения
Нет описания правки
{{В разработке}}
{{Лемма
|about=о длине цикла
|statement= Пусть <tex>G</tex> - произвольный неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>\delta \ge 2</tex>, то в графе <tex>G</tex> существует цикл <tex>C</tex> длиной <tex>l \ge \delta + 1</tex>.
|proof=
Рассмотрим путь максимальной длины <tex>P = v_0 v_1 .. v_s</tex>. Все смежные с <tex>v_0</tex> вершины лежат на <tex>P</tex>. Обозначим <tex>k = max\{i: v_0 v_i \in E\}</tex>. Тогда <tex>\delta \le deg v_0 \le k</tex>. Цикл <tex>C = v_0 v_1 .. v_k v_0</tex> имеет длину <tex>l = k + 1 \ge \delta + 1</tex>
}}
{{Теорема
|about=Дирак
|statement=
|proof=
Пусть <tex>C</tex> - цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \ge n + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex></tex>
По [[Теорема Хватала|теореме Хватала]]: для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>, поскольку левая её часть всегда ложна.
}}
