271
правка
Изменения
Нет описания правки
|statement=
Пусть <tex> G </tex> — [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин <tex>\ G </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=
Приведем доказательство от противного.
Пусть теорема Хватала не верна, есть граф с числом вершин <tex>\ n \ge 3 </tex>, удовлетворяющий условию <tex>\ (*) </tex>, но не гамильтонов.
Будем добавлять в него [[Основные определения теории графов|ребрарёбра]] до тех пор, пока не получим максимально возможный негамильтонов граф <tex> G </tex> (то есть добавление еще одного ребра сделает граф <tex> G </tex> гамильтоновым). Добавление ребер рёбер не противоречит условию <tex>\ (*) </tex>.
Очевидно, что граф <tex>\ K_n </tex> гамильтонов для <tex>\ k \ge 3 </tex>.
Будем считать <tex> G </tex> максимальным негамильтоновым остовным подграфом графа <tex>\ K_n </tex>.
Будем считать, что <tex>\deg u \le \deg v </tex>.
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e</tex>.
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e</tex> : в нем нём обязательно присутствует ребро <tex> e </tex>. <br>
Отбрасывая ребро <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>
<tex>\ S \cap T = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл. Пусть j <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex> : <tex>\ u_1 - u_{j+1} - u_{j+2} - ... - u_n - u_j - u_{j-1} - ... - u_1 </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>
