271
правка
Изменения
Нет описания правки
Т.к. <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>
Доказательство в обратную сторону: <br>
Пусть у нас есть <math>\ n </math> вершин. Из них <math>\ k + p (p \ge 0) </math> или более вершин имеют степень не больше <math>\ k </math>.Расположим вершины в неубывающем порядке их степеней. Очевидно, что вершина с максимальной степенью, не превосходящей <math>\ d_1 \le k, d_2 \le k </math>, будет иметь либо номер <math>... , d_k \le k, ..., d_{k+p} \ le k </math>, либо больше него. Значит <math>\ d_k \le k </math>.
}}
<br>
