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