Изменения

|statement= Пусть <tex>G</tex> {{- --}} произвольный [[Основные определения теории графов#def_undirected_graph_1|неориентированный граф ]] и <tex>\delta</tex> {{--- }} минимальная [[Основные определения теории графов#def_graph_degree_1|степень ]] его вершин. Если <tex>\delta \ge geqslant 2</tex>, то в графе <tex>G</tex> существует [[Основные определения теории графов#def_graph_cycle_1|цикл ]] <tex>C</tex> длиной <tex>l \ge geqslant \delta + 1</tex>.

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

Пусть <tex>G</tex> {{- --}} неориентированный граф и <tex>\delta</tex> {{-- -}} минимальная степень его вершин. Если <tex>n \ge geqslant 3</tex> и <tex>\delta \ge geqslant n/2</tex>, то <tex>G</tex> {{---}} [[Гамильтоновы графы|гамильтонов граф]].|proof=Пусть <tex>C</tex> {{---}} цикл наибольшей длины в графе <tex>G</tex>. По лемме его длина <tex>l \geqslant \delta + 1</tex>. Если <tex>C</tex> - гамильтонов, то теорема доказана. Предположим обратное, т. е. <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь <tex>P = x \dots y : P \cap C = \{y\}</tex> наибольшей длины <tex>m</tex>. Заметим, что по условию <tex>\delta \geqslant n/2</tex>, а значит <tex>\delta \geqslant n - \delta > n - l = |V(G \backslash C)|</tex>. Поэтому каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>.Заметим, что вершина <tex>x</tex> не может быть смежна:* с вершинами из <tex>C</tex>, расстояние от которых до <tex>y</tex> (по <tex>C</tex>) не превышает m. Действительно, пусть вершина <tex>v \in C</tex> и расстояние от <tex>v</tex> до <tex>y</tex> по циклу меньше либо равно <tex>m</tex>. Тогда этот участок цикла можно заменить на <tex>v \rightarrow x \rightarrow P \rightarrow y</tex>, длина которого <tex>m + 1</tex>. Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл <tex>C</tex>.* двум смежным вершинам на <tex>C</tex>. Пусть <tex>u, v \in C</tex> и <tex>\{(u, v), (u, x), (x, v)\} \in E</tex>. Тогда заменив ребро <tex>(u, v)</tex> на <tex>u \rightarrow x \rightarrow v</tex>, увеличим длину цикла на <tex>1</tex>.* вершинам из <tex>G \backslash (C \cup P)</tex>, поскольку <tex>P</tex> максимальный. Получаем <tex>deg\ x \leqslant m + (l - 2m)/2 = l/2 < n/2 \leqslant \delta</tex>. Противоречие.}} ==Альтернативное доказательство== {{Теорема|about=Дирак {{---}} альтернативное доказательство|statement=Пусть <tex>G</tex> {{---}} неориентированный граф и <tex>\delta</tex> {{---}} минимальная степень его вершин. Если <tex>n \geqslant 3</tex> и <tex>\delta \geqslant n/2</tex>, то <tex>G</tex> {{--- }} [[Гамильтоновы графы|гамильтонов граф]].

Пусть Для <tex>C\forall k</tex> - цикл наибольшей длины в графе верна импликация <tex>Gd_k \leqslant k <n/tex>. По лемме его длина <tex>l 2 \ge Rightarrow d_{n-k} \delta + 1geqslant n-k</tex>, поскольку левая её часть всегда ложна. Если Тогда по [[Теорема Хватала | теореме Хватала]] <tex>CG</tex> {{-- -}} гамильтонов, то теорема доказана. Предположим обратное, т. еграф. }} {{Теорема|about = Вывод из [[Теорема Оре|теоремы Оре]]|statement = Пусть <tex>G \backslash C \ne \varnothing</tex>. Рассмотрим путь {{---}} неориентированный граф и <tex>P = x..y : P \cap C = \{y\}delta</tex> наибольшей длины {{---}} минимальная степень его вершин. Если <tex>mn \geqslant 3</tex>. Заметим, что по условию и <tex>\delta \ge geqslant n/2</tex>, а значит то <tex>\delta \ge n - \delta > n - l = |V(G \backslash C)|</tex> и каждая вершина из <tex>G \backslash C</tex> смежна с некоторыми вершинами из <tex>C</tex>{{---}} [[Гамильтоновы графы|гамильтонов граф]].Заметим, что вершина |proof = Возьмем любые неравные вершины <tex>x</tex> не может быть смежна с вершинами из <tex>C</tex>u, расстояние от которых до <tex>y</tex> (по <tex>Cv \in G </tex>) не превышает m, двум смежным вершинам(это противоречило бы максимальности цикла <tex>C</tex>). Она также не может быть смежна с вершинами Тогда <tex>G \backslash (C displaystyle \deg u + \deg v \geqslant \frac n 2 + \cup P)frac n 2 = n </tex>, поскольку . По теореме Оре <tex>PG </tex> максимальный. Получаем <tex>deg\ x \le m + (l {{--- 2m)/2 =l/2 < n/2 \le \delta</tex>. Противоречие}} гамильтонов граф.

Обратим внимание, что эта теорема является следствием из ==См. также==* [[Гамильтоновы графы]]* [[Теорема Хватала]]* [[Теорема Оре]]* [[Теорема Поша]] == Источники информации ==* [[wikipedia:en:Dirac's_Theorem|теоремы ХваталаWikipedia {{---}} Dirac's Theorem]]* Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Действительно''Handbook of Combinatorics'', для <tex>\forall k</tex> верна импликация <tex>d_k \le k < n/Volumes 1 and 2 \Rightarrow d_{n. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-k} \ge n07169-k</tex>, поскольку левая её часть всегда ложнаX.