Изменения
Нет описания правки
|about=Дирак
|statement=
Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ge 3</tex> и <tex>\delta \ge n/2</tex>, то <tex>G</tex> - [[Гамильтоновы графы|гамильтонов граф]].
|proof=
Пусть <tex>C</tex> - цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \ge \delta + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x..y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \ge n/2</tex>, а значит <tex>\delta \ge n - \delta > n - l = |V(G \backslash C)|</tex> и каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>.
|about=Дирак {{---}} альтернативное доказательство
|statement=
Пусть <tex>G</tex> - неориентированный граф и <tex>\delta</tex> - минимальная степень его вершин. Если <tex>n \ge 3</tex> и <tex>\delta \ge n/2</tex>, то <tex>G</tex> - [[Гамильтоновы графы|гамильтонов граф]].
|proof=
Для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k</tex>, поскольку левая её часть всегда ложна. Тогда по [[Теорема Хватала | теореме Хватала]] <tex>G</tex> - гамильтонов граф.
