272
правки
Изменения
Нет описания правки
}}
Из определений <tex> S </tex> и <tex> T </tex> следует, что <tex> S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex>, поэтому <tex> \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 = \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 </tex>.Тогда имеется по крайней мере <tex> \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>.
Так как <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>.
