272
правки
Изменения
Нет описания правки
{{Утверждение
|statement=
<tex> S \cap T = \varnothing emptyset </tex>.
|proof=
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \rightarrow^{e_j} u_{j + 1} \rightarrow u_{j + 2} \rightarrow \ldots \rightarrow u_n \rightarrow^{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов. Значит, <tex> S \cap T </tex>, q.e.d.
Из определений <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 = \varnothing 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 \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>.
