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