Изменения

Исходя из <tex> (*) </tex>, получаем: <tex> d_{n - k} \geq n - k </tex>.

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