Изменения

Т.к. <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 </math> или более вершин имеют степень не больше <math>\ k </math>.Расположим вершины в неубывающем порядке их степеней. Очевидно, что вершина с максимальной степенью, не превосходящей <math>\ k </math>, будет иметь либо номер <math>\ k </math>, либо больше него. Значит <math>\ d_k \le k </math>.