748
правок
Изменения
Нет описания правки
* <tex> d_k \leqslant k </tex>,
* <tex> |\{ d_1, d_2, \ldots, d_k \}| = k </tex>.
<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG | d_v \leqslant k \} \Rightarrow |\{ v \in VG | d_v \leqslant k \}| \geqslant k </tex>, q.e.d.
"<tex> \Leftarrow </tex>" Пусть:
* <tex> p \geqslant 0 </tex>.
Расположим вершины в неубывающем порядке их степеней. <br>
<tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k \leqslant \ldots \leqslant d_{k + p} \leqslant k \Rightarrow d_k \leqslant k </tex>, q.e.d.
}}
* <tex> d_{n - k} \leqslant d_{n - k + 1} \leqslant \ldots \leqslant 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 \} \subseteq \{ v \in VG | d_v \geqslant n - k \} \Rightarrow \{ v \in VG | d_v \geqslant n - k \} \geqslant k + 1 </tex>, q.e.d.
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG | d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</tex>,
Расположим вершины в неубывающем порядке их степеней.
<tex> d_n \geqslant d_{n - 1} \ldots \geqslant d_{n - k} \geqslant \ldots \geqslant d_{n - k - p} \geqslant n - k \Rightarrow d_{n - k} \geqslant n - k </tex>, q.e.d.
}}
# Пусть <tex> d'_k > k </tex>. Тогда первый аргумент импликации всегда ложен, следовательно импликация верна вне зависимости от второго аргумента. Значит, в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
# Пусть <tex> d'_k \leqslant k, \mbox{ } d'_{n - k} \geqslant d_{n - k} \geqslant n - k </tex>. Тогда оба аргумента импликации всегда истинны. Значит, и в этом случае импликация <tex> (*) </tex> верна для последовательности <tex> d' </tex>.
Значит, импликация <tex> (*) </tex> выполняется и для последовательности <tex> d' </tex>, q.e.d.
}}
Пусть <tex> j \in S \cap T </tex>. Тогда получим гамильтонов цикл графа <tex> G </tex>: <tex> u_1 \xrightarrow{e_j} u_{j + 1} \rightarrow \ldots \rightarrow u_n \xrightarrow{f_j} u_j \rightarrow u_{j - 1} \rightarrow \ldots \rightarrow u_1 </tex>, что противоречит условию, что граф негамильтонов.
[[Файл: Hvatal_4.png|270px|thumb|center|]]
Значит, <tex> S \cap T </tex>, q.e.d.
}}
Так как <tex> k = \deg u </tex>, то вершина <tex> u </tex> может быть смежна максимум с <tex> k </tex> из этих <tex> k+1 </tex> вершин. Значит, существует вершина <tex> w </tex>, не являющаяся смежной с <tex> u </tex> и для которой <tex> \deg w \geqslant n - k </tex>. Тогда получим, что <tex> \deg u + \deg w \geqslant k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex> u </tex> и <tex> v </tex>.
Значит, предположение неверно, q.e.d.
}}
