271
правка
Изменения
Нет описания правки
Пусть <math>\ d_1 \le d_1' , ... , d_n \le d_n' </math>.
Тогда <math>\ (*) </math> выполнена и для <math>\ d_1', ... , d_n' </math>
}}
{{Теорема
|about=
Хватала
|statement=
Формулировка приведена выше.
|proof=
Приведем доказательство от противного.
Пусть есть граф , где <math>\ n \ge 3 </math>, удовлетворяющий условию <math>\ (*) </math>, но не гамильтонов.
Будем добавлять в него ребра до тех пор, пока не получим максимально возможный негамильтонов граф '''G'''(т.е. добавление еще одного ребра сделает граф '''G''' гамильтоновым).
Добавление ребер не противоречит условию <math>\ (*) </math>.
Очевидно, что граф <math>\ K_n </math> гамильтонов для <math>\ k \ge 3 </math>.
Будем считать '''G''' максимальным негамильтоновым подграфом графа <math>\ K_n </math>.
Выберем две несмежные вершины U и V графа '''G''' с условием : <math>\ degU + degV </math> - максимально.
Будем считать, <math>\ degU \le degV </math>.
}}
