Изменения
Нет описания правки
{{Лемма
Если <math>\ d_k \le k </math>, то число вершин, степень которых не превосходит <math>\ k </math>, больше или равно <math>\ k </math>.
Верно и обратное утверждение.
|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>.
}}
II
|statement=
Если <math>\ d_nd_{n-k } \ge n-k </math>, то число вершин, степень которых не меньше <math>\ n-k </math>, больше или равно <math>\ k+1 </math>.
Верно и обратное утверждение.
|proof=
Т.к. <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>
{{Теорема
|about=
Хватала
|statement=
|proof=
Приведем доказательство от противного.
