Изменения
Нет описания правки
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k. </tex>
|proof=
* <tex> d_1 \leqslant d_2 \leqslant \ldots \leqslant d_k </tex>,
* <tex> d_k \leqslant k </tex>,
<tex> \{ d_1, d_2, \ldots, d_k \} \subseteq \{ v \in VG \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG \mid d_v \leqslant k \}| \geqslant k </tex>.
* <tex> |\{ v \in VG \mid d_v \leqslant k \}| = k + p </tex>,
* <tex> p \geqslant 0 </tex>.
<tex>\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>
|proof=
* <tex> d_{n - k} \geqslant n - k </tex>,
* <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 \} \subseteq \{ v \in VG \mid d_v \geqslant n - k \} \Rightarrow \{ v \in VG \mid d_v \geqslant n - k \} \geqslant k + 1 </tex>.
* <tex> |\{ v \in VG \mid d_v \geqslant n - k \}| = k + 1 + p, (p \geqslant 0)</tex>,
Расположим вершины в неубывающем порядке их степеней.
Если импликация <tex> (*) </tex> верна для некоторой последовательности степеней <tex> d </tex>, то она верна и для неубывающей последовательности <tex> d' </tex>, мажорирующей <tex> d </tex>.
|proof=
# Пусть Если <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>.
}}
<tex> S \cap T = \emptyset </tex>.
|proof=
[[Файл: Hvatal_4.png|270px|thumb|center|]]
Значит, <tex> S \cap T </tex>.
