272
правки
Изменения
Нет описания правки
1
|statement=
<tex> d_k \leq k \Leftrightarrow |\{ v \in VG : | d_v \leq k \}| \geq k. </tex>
|proof=
* "<tex> \Rightarrow </tex>" Пусть <tex> d_1 \leq d_2 \leq \ldots \leq d_k, d_k \leq k, |\{ d_1, d_2, \ldots, d_k \}| = k </tex>. <br>
<tex> \{ d_1, d_2, \ldots, d_k \} \subset \{ 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> |\{ v \in VG : | d_v \leq k \}| = k + p, p \geq 0 </tex>. Расположим вершины в неубывающем порядке их степеней. <br>
<tex> d_1 \leq d_2 \leq \ldots \leq d_k \leq \ldots \leq d_{k + p} \leq k \Rightarrow d_k \leq k </tex>, q.e.d.
}}
2
|statement=
<tex>\ d_{n - k} \geq n - k \Leftrightarrow |\{ v \in VG : | d_v \geq n - k \}| \geq k + 1. </tex>
|proof=
* "<tex> \Rightarrow </tex>" Пусть <tex> d_{n - k} \geq n - k, d_{n - k} \leq d_{n - k + 1} \leq \ldots \leq d_n, |\{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \}| = k + 1 </tex><br>
<tex> \{ d_{n - k}, d_{n - k + 1}, \ldots , d_n \} \subset \{ 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> |\{ v \in VG : | d_v \geq n - k \}| = k + 1 + p, p \geq 0 </tex>. Расположим вершины в неубывающем порядке их степеней. <br>
<tex> d_n \geq d_{n - 1} \ldots \geq d_{n - k} \geq \ldots \geq d_{n - k - p} \geq n - k \Rightarrow d_{n - k} \geq n - k </tex>, q.e.d.
}}
