Теорема Хватала — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 5 участников)
Строка 1: Строка 1:
 +
{{Определение
 +
|definition=
 +
Пусть [[Основные_определения_теории_графов#.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 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex>. Последовательность <tex> d_1, d_2, \ldots, d_n </tex> называют '''последовательностью степеней''' графа <tex> G </tex>.
 +
}}
 +
 +
{{Лемма
 +
|about=
 +
О добавлении ребра в граф
 +
|statement=
 +
Пусть неориентированный граф <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.
 +
|proof=
 +
''Замечание'': Если в неубывающей последовательности <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>]]
 +
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
 +
Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного.
 +
}}
 +
 
{{Теорема
 
{{Теорема
 
|about=
 
|about=
 
Хватал
 
Хватал
 
|statement=
 
|statement=
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], <tex> n = |VG| \geq 3 </tex> — количество вершин, <tex> d_1 \leq d_2 \leq \ldots \leq d_n </tex> — последовательность степеней. <br>
+
Пусть:
Если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
+
* <tex> G </tex> — [[Отношение_связности,_компоненты_связности#.D0.A1.D0.BB.D1.83.D1.87.D0.B0.D0.B9_.D0.BD.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.D0.BE.D0.B3.D0.BE_.D0.B3.D1.80.D0.B0.D1.84.D0.B0|связный граф]],
<center><tex> d_k \leq k < n/2 \rightarrow d_{n-k} \geq n-k, (*)</tex></center><br>
+
* <tex> n = |VG| \geqslant 3 </tex> — количество вершин,
то граф <tex> G </tex> [[Гамильтоновы графы|гамильтонов]].
+
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n </tex> — его последовательность степеней.
 +
Тогда если <tex> \forall k \in \mathbb N </tex> верна импликация: <br>
 +
<center><tex> d_k \leqslant k < n/2 \Rightarrow d_{n - k} \geqslant n - k, (*) </tex></center>
 +
то граф <tex> G </tex> [[Гамильтоновы_графы#.D0.9E.D1.81.D0.BD.D0.BE.D0.B2.D0.BD.D1.8B.D0.B5_.D0.BE.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|гамильтонов]].
 
|proof=
 
|proof=
 
Для доказательства теоремы, докажем 3 леммы.
 
Для доказательства теоремы, докажем 3 леммы.
# {{Лемма
+
{{Лемма
 +
|about=
 +
1
 
|statement=
 
|statement=
<tex>\ d_k \leq k \Leftrightarrow |\{ v \in |VG| : d_v \leq k \}| \geq k</tex>.
+
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k. </tex>
 
|proof=
 
|proof=
Так как <tex>\ d_1 \le d_2 \le ... \le d_k </tex>, то уже есть <tex>\ k </tex> вершин, степень которых не превосходит <tex>\ k </tex>. Если степени некоторых вершин, следующих за <tex>\ k </tex>, равны <tex>\ d_k </tex>, то число вершин, удовлетворяющих требованию, превышает <tex>\ k </tex>. <br>
+
<tex> \Rightarrow </tex> Пусть:
'''Доказательство в обратную сторону:''' <br>
+
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k </tex>,
пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k + p </tex> <tex> (p \ge 0) </tex> имеют степень не больше <tex>\ k </tex>.
+
* <tex> d_k \leqslant k </tex>,
Расположим вершины в неубывающем порядке их степеней. <tex>\ d_1 \le k, d_2 \le k, ... , d_k \le k, ..., d_{k+p} \le k </tex>. Значит, <tex>\ d_k \le k </tex>.
+
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.
}}
+
<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k </tex>.
  
# {{Лемма
+
<tex> \Leftarrow </tex> Из условия:
|statement=
+
* <tex> |\{ v \in VG \mid d_v \leqslant k \}| = k + p </tex>,
Если <tex>\ d_{n-k} \ge n-k </tex>, то число вершин, степень которых не меньше <tex>\ n-k </tex>, больше или равно <tex>\ k+1 </tex>.
+
* <tex> p \geqslant 0 </tex>.
Верно и обратное утверждение.
+
Расположим вершины в неубывающем порядке их степеней. <br>
|proof=
+
<tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k </tex>.
Так как <tex>\ d_{n-k} \le d_{n-k+1} \le .... \le d_n </tex> и <tex>\ d_{n-k} \ge n-k </tex>, то мы уже получаем <tex>\ d_{n-k}, d_{n-k+1}, ....,  d_n = k + 1 </tex> вершин, удовлетворяющих нашему требованию. Если степени некоторых вершин, предшествующих <tex>\ n-k </tex>, равны <tex>\ d_{n-k} </tex>, то число вершин, удовлетворяющих требованию, превышает <tex>\ k+1 </tex>. <br>
 
'''Доказательство в обратную сторону:''' <br>
 
пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k+p </tex> <tex> (p > 0)</tex> имеют степень не меньше <tex>\ n-k </tex>. Расположим вершины в неубывающем порядке их степеней. Получим: <tex>\ d_n \ge n-k, d_{n-1} \ge n-k, ..., d_{n-k} \ge n-k, ... , d_{n-k-p+1} \ge n-k </tex>. Если <tex> p = 1 </tex>, то <tex> n-k-p+1 = n-k </tex>. Отсюда видно, что <tex>\ d_{n-k} \ge n-k </tex>.
 
}}
 
 
}}
 
}}
  
 
{{Лемма
 
{{Лемма
 
|about=
 
|about=
III
+
2
 
|statement=
 
|statement=
Пусть верно следующее:
+
<tex>\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>
# <tex> (*) </tex> выполнено для последовательности <tex>\ d_1, d_2, ... , d_n </tex>.  
+
|proof=
# <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
+
<tex> \Rightarrow </tex> Пусть:
Тогда <tex>\ (*) </tex> выполнено и для <tex>\ d_1', ... , d_n' </tex>.
+
* <tex> d_{n - k} \geqslant n - k </tex>,
 +
* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n </tex>,
 +
* <tex> |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex>.
 +
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid d_v \geqslant n - k \} \geqslant k + 1 </tex>.
 +
 
 +
<tex> \Leftarrow </tex>:
 +
* <tex> |\{ v \in VG \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</tex>,
 +
Расположим вершины в неубывающем порядке их степеней.
 +
<tex> d_n \geqslant d_{n - 1} \ldots \geqslant d_{n - k} \geqslant \ldots \geqslant d_{n - k - p} \geqslant n - k \Rightarrow d_{n - k} \geqslant n - k </tex>.
 
}}
 
}}
 +
 
{{Лемма
 
{{Лемма
 
|about=
 
|about=
IV
+
3
 
|statement=
 
|statement=
Если <tex>\ (*) </tex> верно для некоторой последовательности степеней, то оно верно и для мажорирующей её последовательности.
+
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
 +
|proof=
 +
# Если <tex> d'_k > k </tex>, то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
 +
# Если <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k </tex>, то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
 +
Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>.
 
}}
 
}}
{{Теорема
+
 
|about=
+
Приведем доказательство от противного.
Хватал
+
 
 +
Пусть существует граф с числом вершин <tex> n \geqslant 3 </tex>, удовлетворяющий <tex> (*) </tex>, но негамильтонов.
 +
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).
 +
По лемме о добавлении ребра и лемме №3 импликация <tex> (*) </tex> остается верной для графа <tex> G </tex>.
 +
Очевидно, что граф <tex>\ K_n </tex> гамильтонов при <tex> k \geqslant 3 </tex>.
 +
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex> K_n </tex>.
 +
 
 +
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex>, такие что <tex> \deg u + \deg v </tex> — максимально.
 +
Будем считать, что <tex> \deg u \leqslant \deg v </tex>.
 +
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.
 +
Рассмотрим гамильтонов цикл графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.
 +
Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = 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> обозначено синим цветом]]
 +
 
 +
{{Утверждение
 
|statement=
 
|statement=
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </tex> по неубыванию.
+
<tex> S \cap T  = \emptyset </tex>.
Если <tex>\forall k</tex> верно <tex> (*) </tex>: <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k) </tex>, то <tex> G </tex> — [[Гамильтоновы графы|гамильтонов]].
 
 
|proof=
 
|proof=
Приведем доказательство от противного.
+
Предположим, что <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов.
Пусть теорема Хватала не верна, то есть существует граф с числом вершин <tex>\ n \ge 3 </tex>, удовлетворяющий <tex>\ (*) </tex>, но негамильтонов.
+
[[Файл: Hvatal_4.png|270px|thumb|center|]]
Будем добавлять в него [[Основные определения теории графов|рёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым).
+
Значит, <tex> S \cap T </tex>.
Важно то, что добавление рёбер не нарушает <tex>\ (*) </tex>.
+
}}
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
+
 
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.
+
Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leqslant \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, <tex> \deg u < n/2 </tex>.
Выберем две несмежные вершины <tex> u </tex> и <tex> v </tex> графа <tex> G </tex> с условием: <tex> \deg u + \deg v </tex> — максимально.
+
 
Будем считать, что <tex>\deg u \le \deg v </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 \leqslant \deg u </tex>. Пусть <tex> k = \deg u = |S| </tex>. Значит, <tex> \exists k </tex> вершин, степень которых не превосходит <tex> k </tex>.
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.
+
 
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e</tex>: в нём обязательно присутствует ребро <tex> e </tex>. <br>
+
По лемме №1: <tex> d_k \leqslant k < n/2 </tex>. В силу импликации <tex> (*) </tex>: <tex> d_{n - k} \geqslant  n - k </tex>.
Отбрасывая ребро <tex> e </tex>, получим гамильтонову (<tex>u</tex>, <tex>v</tex>)-цепь в графе <tex> G </tex>: <tex> u = u_1 - u_2 - ... - u_n = v </tex>. <br>
+
 
Пусть <tex>\ S = \{i|e_i = u_1 u_{i+1} \in E(G)\} </tex>. <br>
+
По лемме №2, <tex> \exists k + 1 </tex> вершин, степень которых не меньше <tex> n - k </tex>.
Пусть <tex>\ T = \{i|f_i = u_i u_n \in E(G)\} </tex>. <br>
+
 
<tex>\ S \cap T  = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл: пусть z <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>:  <tex>\ u_1 - u_{z+1} - u_{z+2} - ... - u_n - u_z - u_{z-1} - ... - u_1 </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 \geqslant n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geqslant k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.
Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex>, поэтому <tex> 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>, то есть <tex>\deg u < n/2 </tex>. <br>
+
 
Так как <tex>\ S \cap T  = \varnothing </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 \le \deg u </tex>. Положим, что <tex>\ k = \deg u </tex>.
+
Значит, предположение неверно.
Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>
 
В силу первой леммы, выполняется: <tex>\ d_k \le k < n/2 </tex>. <br>
 
Исходя из <tex>\ (*) </tex>, получаем: <tex>\ d_{n-k} \ge n-k </tex>. <br>
 
В силу второй леммы, имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex>. <br>
 
Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежна максимум с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит, существует вершина <tex>\ w </tex>, не являющаяся смежной с <tex>\ u </tex> и для которой <tex>\deg w \ge n-k </tex>. Тогда получим, что <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, но это противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>
 
 
}}
 
}}
  
==Литература==
+
==См. также==
* Асанов М,, Баранский В., Расин В. Дискретная математика Графы, матроиды, алгоритмы
+
* [[Гамильтоновы графы]]
 +
* [[Теорема Дирака]]
 +
* [[Теорема Оре]]
 +
 
 +
== Источники информации ==
 +
* Асанов М., Баранский В., Расин В.: ''Дискретная математика: Графы, матроиды, алгоритмы''
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Обходы графов]]
 
[[Категория: Обходы графов]]
 +
[[Категория: Гамильтоновы графы]]

Текущая версия на 19:12, 4 сентября 2022

Определение:
Пусть неориентированный граф [math] G [/math] имеет [math] n [/math] вершин: [math] v_1, v_2, \ldots, v_n [/math]. Пусть [math] d_i = \deg v_i \mbox{ } (i = \overline{1, n}) [/math] и вершины графа упорядочены таким образом, что [math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n [/math]. Последовательность [math] d_1, d_2, \ldots, d_n [/math] называют последовательностью степеней графа [math] G [/math].


Лемма (О добавлении ребра в граф):
Пусть неориентированный граф [math] G' [/math] получен из неориентированного графа [math] G [/math] добавлением одного нового ребра [math] e [/math]. Тогда последовательность степеней графа [math] G [/math] мажорируется последовательностью степеней графа [math] G' [/math].
Доказательство:
[math]\triangleright[/math]

Замечание: Если в неубывающей последовательности [math] d_1, d_2, \ldots, d_n [/math] увеличить на единицу число [math] d_i [/math], а затем привести последовательность к неубывающему виду, переставив число [math] d_i + 1 [/math] на положенное место [math] j [/math], то исходная последовательность будет мажорироваться полученной. Если [math]j = i[/math], то утверждение леммы, очевидно, выполняется. Пусть [math]j \neq i[/math].

Исходная последовательность степеней [math] d [/math]
  • Рассмотрим элементы с номерами [math] s = \overline{1, i - 1} [/math]. Они не изменились, следовательно мажорируются собой.
  • Рассмотрим элементы с номерами [math] s = \overline{i, j - 1} [/math]. [math] s [/math]-й элемент полученной последовательности равен [math] s + 1 [/math]-му элементу исходной. [math] d_s \leqslant d_{s + 1} \Rightarrow d_s \leqslant d'_s = d_{s + 1} [/math].
  • Расмотрим [math]j[/math]-ый элемент. Имеем [math]d'_j \ge d'_{j-1} = d_{j} [/math].
  • Рассмотрим элементы с номерами [math] s = \overline{j + 1, n} [/math]. Они не изменились, следовательно мажорируются собой.
Новая последовательность степеней [math] d' [/math]

При добавлении в граф ребра [math] e = uv, \mbox{ } (u \neq v) [/math], степени вершин [math] u [/math] и [math] v [/math] увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.

Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного.
[math]\triangleleft[/math]
Теорема (Хватал):
Пусть:
  • [math] G [/math]связный граф,
  • [math] n = |VG| \geqslant 3 [/math] — количество вершин,
  • [math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_n [/math] — его последовательность степеней.

Тогда если [math] \forall k \in \mathbb N [/math] верна импликация:

[math] d_k \leqslant k \lt n/2 \Rightarrow d_{n - k} \geqslant n - k, (*) [/math]
то граф [math] G [/math] гамильтонов.
Доказательство:
[math]\triangleright[/math]

Для доказательства теоремы, докажем 3 леммы.

Лемма (1):
[math] d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k. [/math]
Доказательство:
[math]\triangleright[/math]

[math] \Rightarrow [/math] Пусть:

  • [math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k [/math],
  • [math] d_k \leqslant k [/math],
  • [math] |\{ d_1, d_2, \ldots, d_k \}| = k [/math].

[math] \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k [/math].

[math] \Leftarrow [/math] Из условия:

  • [math] |\{ v \in VG \mid d_v \leqslant k \}| = k + p [/math],
  • [math] p \geqslant 0 [/math].

Расположим вершины в неубывающем порядке их степеней.

[math] d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k [/math].
[math]\triangleleft[/math]
Лемма (2):
[math]\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. [/math]
Доказательство:
[math]\triangleright[/math]

[math] \Rightarrow [/math] Пусть:

  • [math] d_{n - k} \geqslant n - k [/math],
  • [math] d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant d_n [/math],
  • [math] |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 [/math].

[math] \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subseteq \{ v \in VG \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid d_v \geqslant n - k \} \geqslant k + 1 [/math].

[math] \Leftarrow [/math]:

  • [math] |\{ v \in VG \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)[/math],

Расположим вершины в неубывающем порядке их степеней.

[math] d_n \geqslant d_{n - 1} \ldots \geqslant d_{n - k} \geqslant \ldots \geqslant d_{n - k - p} \geqslant n - k \Rightarrow d_{n - k} \geqslant n - k [/math].
[math]\triangleleft[/math]
Лемма (3):
Если импликация [math] (*) [/math] верна для некоторой последовательности степеней [math] d [/math], то она верна и для неубывающей последовательности [math] d' [/math], мажорирующей [math] d [/math].
Доказательство:
[math]\triangleright[/math]
  1. Если [math] d'_k \gt k [/math], то первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация [math] (*) [/math] верна для последовательности [math] d' [/math].
  2. Если [math] d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k [/math], то оба аргумента импликации всегда истинны. Значит, и в этом случае импликация [math] (*) [/math] верна для последовательности [math] d' [/math].
Значит, импликация [math] (*) [/math] выполняется и для последовательности [math] d' [/math].
[math]\triangleleft[/math]

Приведем доказательство от противного.

Пусть существует граф с числом вершин [math] n \geqslant 3 [/math], удовлетворяющий [math] (*) [/math], но негамильтонов. Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф [math] G [/math] (то есть добавление еще одного ребра сделает граф [math] G [/math] гамильтоновым). По лемме о добавлении ребра и лемме №3 импликация [math] (*) [/math] остается верной для графа [math] G [/math]. Очевидно, что граф [math]\ K_n [/math] гамильтонов при [math] k \geqslant 3 [/math]. Будем считать [math] G [/math] максимальным негамильтоновым остовным подграфом графа [math] K_n [/math].

Выберем две несмежные вершины [math] u [/math] и [math] v [/math] графа [math] G [/math], такие что [math] \deg u + \deg v [/math] — максимально. Будем считать, что [math] \deg u \leqslant \deg v [/math]. Добавив к [math] G [/math] новое ребро [math] e = uv [/math], получим гамильтонов граф [math] G + e [/math]. Рассмотрим гамильтонов цикл графа [math] G + e [/math]: в нём обязательно присутствует ребро [math] e [/math]. Отбрасывая ребро [math] e [/math], получим гамильтонову [math] (u, v) [/math]-цепь в графе [math] G [/math]: [math] u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v [/math].

Пусть [math] S = \{ i \mid e_i = u_1 u_{i + 1} \in EG\}, T = \{ i \mid f_i = u_i u_n \in EG\} [/math].

Множество [math] S [/math] обозначено красным цветом, множество [math] T [/math] обозначено синим цветом
Утверждение:
[math] S \cap T = \emptyset [/math].
[math]\triangleright[/math]

Предположим, что [math] j \in S \cap T [/math]. Тогда получим гамильтонов цикл графа [math] G [/math]: [math] u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 [/math], что противоречит условию, что граф негамильтонов.

Hvatal 4.png
Значит, [math] S \cap T [/math].
[math]\triangleleft[/math]

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

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

По лемме №1: [math] d_k \leqslant k \lt n/2 [/math]. В силу импликации [math] (*) [/math]: [math] d_{n - k} \geqslant n - k [/math].

По лемме №2, [math] \exists k + 1 [/math] вершин, степень которых не меньше [math] n - k [/math].

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

Значит, предположение неверно.
[math]\triangleleft[/math]

См. также

Источники информации

  • Асанов М., Баранский В., Расин В.: Дискретная математика: Графы, матроиды, алгоритмы