272
правки
Изменения
Нет описания правки
Так как <tex> S \cap T = \varnothing </tex>, ни одна вершина <tex> u_j </tex> не смежна с <tex> v = u_n </tex> (для <tex> j \in S </tex>). В силу выбора <tex> u </tex> и <tex> v </tex>, получим, что <tex> \deg u_j \leq \deg u </tex>. Пусть <tex> k = \deg u \Rightarrow \exists |S| = \deg u = k </tex> вершин, степень которых не превосходит <tex> k </tex>.
По лемме №1: <tex> d_k \leq k < n/2 </tex>. Исходя из В силу импликации <tex> (*) </tex>, получаем: <tex> d_{n - k} \geq n - k </tex>.
По лемме №2, <tex> \exists k + 1 </tex> вершин, степень которых не меньше <tex> n - k </tex>.
