Изменения
Нет описания правки
Пусть <tex>\ S = \{i|e_i = u_1 u_{i+1} \in E(G)\} </tex> <br>
Пусть <tex>\ T = \{i|f_i = u_i u_n \in E(G)\} </tex> <br>
<tex>\ S \cap T = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл. Пусть j <tex> \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex> : <tex>\ u_1 - u_{j+1} - u_{j+2} - ... - u_n - u_j - u_{j-1} - ... - u_1 </tex>.Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex> , поэтому <tex> 2\deg u \le \deg u + \deg v = |S| + |T| = |S \cup T| < n </tex>, то есть <tex>\deg u < n/2 </tex> . <br>Так как <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 \le \deg u </tex>. Положим <tex>\ k = \deg u </tex>.
Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>
В силу леммы(I) выполняется : <tex>\ d_k \le k < n/2 </tex> . <br>По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex> . <br>В силу леммы(II) имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex> . <br>
Так как <tex>\ k = \deg u </tex>, то вершина <tex>\ u </tex> может быть смежна, самое большее, с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ w </tex>, несмежная с <tex>\ u </tex>, и для которой <tex>\deg w \ge n-k </tex>. Но тогда получим <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>
}}
