271
правка
Изменения
Нет описания правки
I
|statement=
<span style="display:inline;"><span style="display:table-cell; border:{{{width|1px}}} {{{style|solid}}} {{{color|#000}}};">Если <tex>\ d_k \le k </tex>, то число вершин, степень которых не превосходит <tex>\ k </tex>, больше или равно <tex>\ k </tex>. Верно и обратное утверждение.</span></span>
|proof=
Так как <tex>\ d_1 \le d_2 \le ... \le d_k </tex>, то уже есть <tex>\ k </tex> вершин, степень которых не превосходит <tex>\ k </tex>. Если степени некоторых вершин, следующих за <tex>\ k </tex> равны <tex>\ d_k </tex>, то число вершин, удовлетворяющих требованию, превышает <tex>\ k </tex>. <br>
II
|statement=
<span style="display:inline;"><span style="display:table-cell; border:{{{width|1px}}} {{{style|solid}}} {{{color|#000}}};">Если <tex>\ d_{n-k} \ge n-k </tex>, то число вершин, степень которых не меньше <tex>\ n-k </tex>, больше или равно <tex>\ k+1 </tex>.Верно и обратное утверждение. </span> </span>
|proof=
Так как <tex>\ d_{n-k} \le d_{n-k+1} \le .... \le d_n </tex> и <tex>\ d_{n-k} \ge n-k </tex>, то мы уже получаем <tex>\ d_{n-k}, d_{n-k+1}, ...., d_n = k + 1 </tex> вершину, удовлетворяющую нашему требованию. Если степени некоторых вершин, предшествующих <tex>\ n-k </tex> равны <tex>\ d_{n-k} </tex>, то число вершин, подходящих нашему требованию, превышает <tex>\ k+1 </tex> <br>
III
|statement=
<span style="display:inline;"><span style="display:table-cell; border:{{{width|1px}}} {{{style|solid}}} {{{color|#000}}};">Пусть <tex>\ (*) </tex> выполнена для последовательности <tex>\ d_1, d_2, ... , d_n </tex>.
Пусть <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
Тогда <tex>\ (*) </tex> выполнена и для <tex>\ d_1', ... , d_n' </tex></span></span>
}}
{{Лемма
|about=
IV
|statement=
<span style="display:inline;"><span style="display:table-cell; border:{{{width|1px}}} {{{style|solid}}} {{{color|#000}}};">Если условие <tex>\ (*) </tex> верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности.</span></span>
}}
{{Теорема
|about=
По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex>. <br>
В силу леммы(II) имеется по крайней мере <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 n-k </tex>. Но тогда получим <tex>\deg u + \deg w \ge k + (n - k) = n > \deg u + \deg v </tex>, что противоречит выбору <tex>\ u </tex> и <tex>\ v </tex>. <br>
}}
