Изменения
Нет описания правки
Все <math>\ d_i </math> расположены в порядке неубывания.<br><math>\ (*): </math> <math>\forall k</math> верна импликация <math>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k)</math> <br>
{{Лемма
|about=
|proof=
Т.к. <math>\ d_1 \le d_2 \le ... \le d_k </math>, то уже есть <math>\ k </math> вершин, степень которых не превосходит <math>\ k </math>. Если степени некоторых вершин, следующих за <math>\ k </math> равны <math>\ d_k </math>, то число вершин, удовлетворяющих требованию, превышает <math>\ k </math>.
}}
<br>
{{Лемма
Т.к. <math>\ d_{n-k} \le d_{n-k+1} \le .... \le d_n </math> и <math>\ d_{n-k} \ge n-k </math>, то мы уже получаем <math>\ d_{n-k}, d_{n-k+1}, ...., d_n = k + 1 </math> вершину, удовлетворяющую нашему требованию. Если степени некоторых вершин, предшествующих <math>\ n-k </math> равны <math>\ d_{n-k} </math>, то число вершин, подходящих нашему требованию, превышает <math>\ k+1 </math>
}}
<br>
{{Лемма
Тогда <math>\ (*) </math> выполнена и для <math>\ d_1', ... , d_n' </math>
}}
<br>
{{Лемма
|about=
Выберем две несмежные вершины U и V графа '''G''' с условием : <math>\ degU + degV </math> - максимально.
Будем считать, <math>\ degU \le degV </math>.
Добавив к '''G''' новое ребро <math>\ e = UV </math>, получим гамильтонов граф '''G''' + UV.
Рассмотрим гамильтонов цикл графа '''G''' + UV : в нем обязательно присутствует ребро UV. <br>
Отбрасывая ребро UV, получим гамильтонову (U, V)-цепь в графе '''G''' : <math>\ U = U_1 - U_2 - ... - U_n = V </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.<br>
В силу леммы(I) выполняется : <math>\ d_k \le k < n/2 </math> <br>
По условию <math>\ (*) </math> получаем : <math>\ d_{n-k} \ge n-k </math> <br>
