Изменения

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