271
правка
Изменения
Нет описания правки
В [[Основные определения теории графов|графе]]: <tex>\ G </tex>, состоящем из <tex>\ n </tex> [[Основные определения теории графов|вершин]], <tex>\ d_i </tex> - [[Основные определения теории графов|степень]] <tex>\ i </tex> - ой вершины. <br>
Все <tex>\ d_i </tex> расположены в порядке неубывания. <br>
<tex>\ (*): </tex> <tex>\forall k</tex> верна импликация <tex>(d_k \le k < n/2 \Rightarrow d_{n-k} \ge n-k)</tex> <br>
Верно и обратное утверждение.
|proof=
Доказательство в обратную сторону: <br>
Пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k + p (p \ge 0) </tex> вершин имеют степень не больше <tex>\ k </tex>.
Верно и обратное утверждение.
|proof=
Доказательство в обратную сторону: <br>
Пусть у нас есть <tex>\ n </tex> вершин. Из них <tex>\ k+p (p > 0)</tex> вершин имеют степень не меньше <tex>\ n-k </tex>. Расположим вершины в неубывающем порядке их степеней. Получим : <tex>\ d_n \ge n-k, d_{n-1} \ge n-k, ..., d_{n-k} \ge n-k, ... , d_{n-k-p+1} \ge n-k </tex>. Если p = 1, то n-k-p+1 = n-k. Отсюда видно, что <tex>\ d_{n-k} \ge n-k </tex>.
Пусть <tex>\ d_1 \le d_1' , ... , d_n \le d_n' </tex>.
Тогда <tex>\ (*) </tex> выполнена и для <tex>\ d_1', ... , d_n' </tex>
}}
<br>
|statement=
Если условие <tex>\ (*) </tex> верно для некоторой последовательности степеней, то оно верно и для мажорирующей ее последовательности.
}}
<br>
{{Теорема
|about=
|statement=
Пусть '''G''' - [[Отношение связности, компоненты связности|связный граф]], количество вершин которого не меньше 3. Упорядочим степени вершин '''G''' по неубыванию.
По условию <tex>\ (*) </tex> получаем : <tex>\ d_{n-k} \ge n-k </tex> <br>
В силу леммы(II) имеется по крайней мере <tex>\ k+1 </tex> вершин, степень которых не меньше <tex>\ n-k </tex> <br>
Так как <tex>\ k = degU \deg U </tex>, то вершина <tex>\ U </tex> может быть смежна, самое большее, с <tex>\ k </tex> из этих <tex>\ k+1 </tex> вершин. Значит существует вершина <tex>\ W </tex>, несмежная с <tex>\ U </tex>, и для которой <tex>\ degW \ge n-k </tex>. Но тогда получим <tex>\ degU deg U + degW \deg W \ge k + (n - k) = n > degU \deg U + degV \deg V </tex>, что противоречит выбору <tex>\ U </tex> и <tex>\ V </tex>. <br>
}}
==Литература==
* Асанов М,, Баранский В., Расин В. - Дискретная математика - Графы, матроиды, алгоритмы
