748
правок
Изменения
Нет описания правки
1
|statement=
<tex> d_k \leqslant k \Leftrightarrow |\{ v \in VG | \mid d_v \leqslant k \}| \geqslant k. </tex>
|proof=
"<tex> \Rightarrow </tex>" Пусть:
* <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 | \mid d_v \leqslant k \} \Rightarrow |\{ v \in VG | \mid d_v \leqslant k \}| \geqslant k </tex>.
"<tex> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG | \mid d_v \leqslant k \}| = k + p </tex>,
* <tex> p \geqslant 0 </tex>.
Расположим вершины в неубывающем порядке их степеней. <br>
2
|statement=
<tex>\ d_{n - k} \geqslant n - k \Leftrightarrow |\{ v \in VG | \mid d_v \geqslant n - k \}| \geqslant k + 1. </tex>
|proof=
"<tex> \Rightarrow </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 \}| = k + 1 </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> \Leftarrow </tex>" Пусть:
* <tex> |\{ v \in VG | \mid 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>.
Отбрасывая ребро <tex> e </tex>, получим гамильтонову <tex> (u, v) </tex>-цепь в графе <tex> G </tex>: <tex> u = u_1 \rightarrow u_2 \rightarrow \ldots \rightarrow u_n = v </tex>.
Пусть <tex> S = \{ i | \mid e_i = u_1 u_{i + 1} \in EG\}, T = \{ i |\mid f_i = u_i u_n \in EG\} </tex>.
[[Файл: Hvatal_3.png|330px|thumb|center|Множество <tex> S </tex> обозначено красным цветом, множество <tex> T </tex> обозначено синим цветом]]
