271
правка
Изменения
Нет описания правки
Исходя из условия <tex>\ (*) </tex>, получаем: <tex>\ d_{n-k} \ge n-k </tex>. <br>
В силу второй леммы, имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex>. <br>
Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежна максимум с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит , существует вершина <tex>\ w </tex>, не являющаяся смежной с <tex>\ u </tex> и для которой <tex>\deg w \ge n-k </tex>. Тогда получим, что <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, но это противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>
}}
