272
правки
Изменения
Нет описания правки
Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} \Rightarrow 2 \deg u \leq \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>. Значит, <tex> \deg u < n/2 </tex>.
Так как <tex> S \cap T = \emptyset </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 = |S| </tex>. Значит, <tex> \exists </tex> ровно <tex> k </tex> вершин, степень которых не превосходит <tex> k </tex>.
По лемме №1: <tex> d_k \leq k < n/2 </tex>. В силу импликации <tex> (*) </tex>: <tex> d_{n - k} \geq n - k </tex>.
