Изменения

Пусть [[Основные_определения_теории_графов#.D0.9D.D0.B5.D0.BE.D1.80.D0.B8.D0.B5.D0.BD.D1.82.D0.B8.D1.80.D0.BE.D0.B2.D0.B0.D0.BD.D0.BD.D1.8B.D0.B5_.D0.B3.D1.80.D0.B0.D1.84.D1.8B|неориентированный граф]] <tex> G </tex> имеет <tex> n </tex> вершин: <tex> v_1, v_2, \ldots, v_n </tex>. Пусть <tex> d_i = \deg v_i \mbox{ } (i = \overline{1, n}) </tex> и вершины графа упорядочены таким образом, что <tex> d_1 \leq leqslant d_2 \leq leqslant \ldots \leq leqslant d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.

''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место<tex> j </tex>, то исходная последовательность будет мажорироваться полученной.Если <tex>j = i</tex>, то утверждение леммы, очевидно, выполняется. Пусть <tex>j \neq i</tex>.[[Файл: Hvatal_1.png|270px|thumb|center|Исходная последовательность степеней <tex> d </tex>]] * Рассмотрим элементы с номерами <tex> s = \overline{1, i - 1} </tex>. Они не изменились, следовательно мажорируются собой.* Рассмотрим элементы с номерами <tex> s = \overline{i, j - 1} </tex>. <tex> s </tex>-й элемент полученной последовательности равен <tex> s + 1 </tex>-му элементу исходной. <tex> d_s \leqslant d_{s + 1} \Rightarrow d_s \leqslant d'_s = d_{s + 1} </tex>.* Расмотрим <tex>j</tex>-ый элемент. Имеем <tex>d'_j \ge d'_{j-1} = d_{j} </tex>.* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.[[Файл: Hvatal_2.png|290px|thumb|center|Новая последовательность степеней <tex> d' </tex>]]

Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.

* <tex> n = |VG| \geq geqslant 3 </tex> — количество вершин,* <tex> d_1 \leq leqslant d_2 \leq leqslant \ldots \leq leqslant d_n </tex> — его последовательность степеней.

<center><tex> d_k \leq leqslant k < n/2 \rightarrow Rightarrow d_{n - k} \geq geqslant n - k, (*) </tex></center>

<tex> d_k \leq leqslant k \Leftrightarrow |\{ v \in VG | \mid d_v \leq leqslant k \}| \geq geqslant k. </tex>

"<tex> \Rightarrow </tex>" Пусть:* <tex> d_1 \leq leqslant d_2 \leq leqslant \ldots \leq leqslant d_k </tex>,* <tex> d_k \leq leqslant k </tex>,

<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG | \mid d_v \leq leqslant k \} \Rightarrow |\{ v \in VG | \mid d_v \leq leqslant k \}| \geq geqslant k </tex>, q.e.d.

"<tex> \Leftarrow </tex>" ПустьИз условия:* <tex> |\{ v \in VG | \mid d_v \leq leqslant k \}| = k + p </tex>,* <tex> p \geq geqslant 0 </tex>.

<tex> d_1 \leq leqslant d_2 \leq leqslant \ldots \leq leqslant d_k \leq leqslant \ldots \leq leqslant d_{k + p} \leq leqslant k \Rightarrow d_k \leq leqslant k </tex>, q.e.d.

<tex>\ d_{n - k} \geq geqslant n - k \Leftrightarrow |\{ v \in VG | \mid d_v \geq geqslant n - k \}| \geq geqslant k + 1. </tex>

"<tex> \Rightarrow </tex>" Пусть:* <tex> d_{n - k} \geq geqslant n - k </tex>,* <tex> d_{n - k} \leq leqslant d_{n - k + 1} \leq leqslant \ldots \leq leqslant d_n </tex>,

<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG | \mid d_v \geq geqslant n - k \} \Rightarrow \{ v \in VG | \mid d_v \geq geqslant n - k \} \geq geqslant k + 1 </tex>, q.e.d.

"<tex> \Leftarrow </tex>" Пусть:* <tex> |\{ v \in VG | \mid d_v \geq geqslant n - k \}| = k + 1 + p </tex>,* <tex> (p \geq geqslant 0 )</tex>.,

<tex> d_n \geq geqslant d_{n - 1} \ldots \geq geqslant d_{n - k} \geq geqslant \ldots \geq geqslant d_{n - k - p} \geq geqslant n - k \Rightarrow d_{n - k} \geq geqslant n - k </tex>, q.e.d.

# Пусть Если <tex> d'_k > k </tex>. Тогда , то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.# Пусть Если <tex> d'_k \leq leqslant k, \mbox{ } d'_{n - k} \geq geqslant d_{n - k} \geq geqslant n - k </tex>. Тогда , то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>, q.e.d.

Пусть существует граф с числом вершин <tex> n \geq geqslant 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.

Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geq geqslant 3 </tex>.

Будем считать, что <tex> \deg u \leq leqslant \deg v </tex>.

Пусть <tex> S = \{ i | \mid e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |\mid f_i = u_i u_n \in EG\} </tex>.[[Файл: Hvatal_3.png|330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]

Пусть Предположим, что <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \rightarrow^xrightarrow{e_j} u_{j + 1} \rightarrow u_{j + 2} \rightarrow \ldots \rightarrow u_n \rightarrow^xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов. [[Файл: Hvatal_4.png|270px|thumb|center|]]Значит, <tex> S \cap T </tex>, q.e.d.

Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leq leqslant \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, <tex> \deg u < n/2 </tex>.

Так как <tex> S \cap T = \emptyset </tex>, ни одна вершина <tex> u_j </tex> не смежна с <tex> v = u_n </tex> (для <tex> j \in S </tex>). В силу выбора <tex> u </tex> и <tex> v </tex>, получим, что <tex> \deg u_j \leq leqslant \deg u </tex>. Пусть <tex> k = \deg u \Rightarrow \exists = |S| = </tex>. Значит, <tex> \deg u = exists k </tex> вершин, степень которых не превосходит <tex> k </tex>.

По лемме №1: <tex> d_k \leq leqslant k < n/2 </tex>. В силу импликации <tex> (*) </tex>: <tex> d_{n - k} \geq geqslant n - k </tex>.

Так как <tex> k = \deg u </tex>, то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+1 </tex> вершин. Значит, существует вершина <tex> w </tex>, не являющаяся смежной с <tex> u </tex> и для которой <tex> \deg w \geq geqslant n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geq geqslant k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.

Значит, предположение неверно, q.e.d.

== Литература См. также==* [[Гамильтоновы графы]]* [[Теорема Дирака]]* [[Теорема Оре]] == Источники информации ==