271
правка
Изменения
Нет описания правки
}}
Прежде , чем доказать теорему, добавим несколько лемм.
{{Лемма
III
|statement=
Пусть '''<math>\ (*)''' </math> выполнена для последовательности <math>\ d_1, d_2, ... , d_n </math>.
Пусть <math>\ d_1 \le d_1' , ... , d_n \le d_n' </math>.
Тогда <math>\ (*) </math> выполнена и для <math>\ d_1', ... , d_n' </math>
}}
{{Лемма
|about=
IV
|statement=
Если условие <math>\ (*) </math> верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности
}}
<br>
|proof=
Приведем доказательство от противного.
Пусть теорема Хватала не верна, есть граф , где <math>\ n \ge 3 </math>, удовлетворяющий условию <math>\ (*) </math>, но не гамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым).
Добавление ребер не противоречит условию <math>\ (*) </math>.
Будем считать, <math>\ degU \le degV </math>.
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.
Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. Отбрасывая ребро UV, получим гамильтонову цепь (U, V) -цепь в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </math>. <br>
Пусть <math>\ S = \{i|e_i = U_1 U_{i+1} \in E(G)\} </math> <br>
Пусть <math>\ T = \{i|f_i = U_i U_n \in E(G)\} </math> <br>
<math>\ S \cap T = \empty </math>, иначе в графе '''G''' есть гамильтонов цикл. Пусть j <math> \in S \cap T </math>. Тогда получим гамильтонов цикл графа '''G''' : <math>\ U_1 - U_{j+1} - U_{j+2} - ... - U_n - U_j - U_{j-1} - ... - U_1 </math> <br>
Из определений <math>\ S </math> и <math>\ T </math> следует, что <math>\ S \cup T \sube \{1, 2, ..., n - 1 \} </math> , поэтому <math>\ 2degU \le degU + degV = |S| + |T| = |S \cup T| < n </math>, т.е. <math>\ degU < n/2 </math> <br>Т.к. <math>\ S \cap T = \empty </math>, ни одна вершина <math>\ U_j </math> не смежна с <math>\ V = U_n </math> (<math> для j \in S </math>). Отсюда в силу выбора <math>\ U </math> и <math>\ V </math> имеем <math>\ degU_j \le degU </math>. Положим <math>\ k = degU </math>.
Тогда имеется по крайней мере <math>\ |S| = degU = k </math> вершин, степень которых не превосходит k.
В силу леммы(I) выполняется : <math>\ d_k \le k < n/2 </math> <br>
По условию <math>\ (*) </math> получаем : <math>\ d_{n-k} \ge n-k </math> <br>
В силу луммылеммы(II) имеется по крайней мере <math>\ k+1 </math> вершин, степень которых не меньше <math>\ n-k </math> <br>Так как <math>\ k = degU </math>, то вершина <math>\ U </math> может быть смежна, самое большоебольшее, с <math>\ k </math> из этих <math>\ k+1 </math> вершин. Значит существует вершина <math>\ W </math>, несмежная с <math>\ U </math>, для которой <math>\ degW \ge n-k </math>. Но тогда получим <math>\ degU + degW \ge k + (n - k) = n > degU + degV </math>, что противоречит выбору <math>\ U </math> и <math>\ V </math>. <br>
}}
