271
правка
Изменения
Нет описания правки
{{Теорема
|about=
Хватала
|statement=
Пусть '''G''' - связный граф, количество вершин которого не меньше 3. Упорядочим степени вершин '''G''' по неубыванию.
Если для <math>\forall k</math> верна импликация <math>d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k (*) </math> (*),
то '''G''' - гамильтонов.
}}
Если <math>\ d_n-k \ge n-k </math>, то число вершин, степень которых не меньше <math>\ n-k </math>, больше или равно <math>\ k+1 </math>.
Верно и обратное утверждение.
}}
{{Лемма
|about=
III
|statement=
Пусть '''(*)''' выполнена для последовательности <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>
}}
