Изменения

Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>

В силу первой леммы, выполняется: <tex>\ d_k \le k < n/2 </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>