272
правки
Изменения
Нет описания правки
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место, то исходная последовательность будет мажорироваться полученной.
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.
}}
* <tex> d_k \leq k </tex>,
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.
<tex> \{ d_1, d_2, \ldots, d_k \} \subset subseteq \{ v \in VG | d_v \leq k \} \Rightarrow |\{ v \in VG | d_v \leq k \}| \geq k </tex>, q.e.d.
"<tex> \Leftarrow </tex>" Пусть:
* <tex> d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n </tex>,
* <tex> |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex>.
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subset subseteq \{ v \in VG | d_v \geq n - k \} \Rightarrow \{ v \in VG | d_v \geq n - k \} \geq k + 1 </tex>, q.e.d.
"<tex> \Leftarrow </tex>" Пусть:
Добавив к <tex> G </tex> новое ребро <tex> e = uv </tex>, получим гамильтонов граф <tex> G + e </tex>.
Рассмотрим [[Гамильтоновы графы|гамильтонов цикл]] графа <tex> G + e </tex>: в нём обязательно присутствует ребро <tex> e </tex>.
Отбрасывая ребро <tex> e </tex>, получим гамильтонову (<tex> (u, v ) </tex>)-цепь в графе <tex> G </tex>: <tex> u = u_1 - \rightarrow u_2 - ... - \rightarrow \ldots \rightarrow u_n = v </tex>. <br> Пусть <tex>\ S = \{i|e_i = u_1 u_{i+1} \in E(G)EG\} </tex>. <br>Пусть <tex>\ , T = \{i|f_i = u_i u_n \in E(G)EG\} </tex>. <br> Докажем, что <tex>\ S \cap T = \varnothing </tex>, иначе в графе <tex> G </tex> есть гамильтонов цикл.: пусть z Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex>u_1 \ u_1 - rightarrow^{e_j} u_{zj +1} - \rightarrow u_{zj +2} - ... - \rightarrow \ldots \rightarrow u_n - u_z - \rightarrow^{f_j} u_j \rightarrow u_{zj -1} - ... - \rightarrow \ldots \rightarrow u_1 </tex>. Из определений <tex>\ S </tex> и <tex>\ T </tex> следует, что <tex>\ S \cup T \subseteq \{1, 2, ..., n - 1 \} </tex>, поэтому <tex> 2\deg u \le leq \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 leq \deg u </tex>. Положим, что <tex>\ k = \deg u </tex>.Тогда имеется по крайней мере <tex>\ |S| = \deg u = k </tex> вершин, степень которых не превосходит k. <br>В силу первой леммыПо лемме №1, выполняется: <tex>\ d_k \le leq k < n/2 </tex>. <br> Исходя из <tex>\ (*) </tex>, получаем: <tex>\ d_{n-k} \ge geq n-k </tex>. <br>В силу По второй леммылемме, имеется по крайней мере <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 geq n-k </tex>. Тогда получим, что <tex>\deg u + \deg w \ge geq k + (n - k) = n > \deg u + \deg v </tex>, но это что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br> Значит, предположение неверно, q.e.d.
}}
