272
правки
Изменения
Нет описания правки
Пусть неориентированный граф <tex> G' </tex> получен из неориентированного графа <tex> G </tex> добавлением одного нового ребра <tex> e </tex>. Тогда последовательность степеней графа <tex> G </tex> мажорируется последовательностью степеней графа <tex> G' </tex>.
|proof=
''Замечание'': Если в неубывающей последовательности <tex> d_1, d_2, \ldots, d_n </tex> увеличить на единицу число <tex> d_i </tex>, а затем привести последовательность к неубывающему виду, переставив число <tex> d_i + 1 </tex> на положенное место<tex> j </tex>, то исходная последовательность будет мажорироваться полученной.* Рассмотрим элементы с номерами <tex> s = \overline{1, i} </tex>. Они не изменились, следовательно мажорируются собой.* Рассмотрим элементы с номерами <tex> s = \overline{i + 1, j + 1} </tex>. <tex> s + 1 </tex>-й элемент исходной последовательности равен <tex> s </tex>-му элементу полученной. <tex> d_s \leq d_{s + 1} \Rightarrow d_s \leq d'_s </tex>.* Рассмотрим элементы с номерами <tex> s = \overline{j + 1, n} </tex>. Они не изменились, следовательно мажорируются собой.
При добавлении в граф ребра <tex> e = uv, \mbox{ } (u \neq v) </tex>, степени вершин <tex> u </tex> и <tex> v </tex> увеличатся на единицу. Для доказательства леммы, дважды воспользуемся замечанием.
Значит, последовательность степеней полученного графа мажорирует последовательность степеней исходного, q.e.d.
