137
правок
Изменения
Нет описания правки
<tex>\sum\limits_{i=1}^n \alpha_i + \sum\limits_{i=1}^n \beta_i + \sum\limits_{i=1}^n \gamma_i \geqslant kn ~~~ \textbf{(2)}</tex>
Заметим, что все множества рёбер <tex>A_i\subset E(G')</tex> и <tex>B_j\subset F</tex> не пересекаются (так как <tex>E(G') = E(G) \setminus F</tex>) и ведут во множество <tex>S</tex>. Поэтому сумма <tex>\sum\limits_{i=1}^t |A_i| + \sum\limits_{i=1}^t |B_i| = \sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i</tex> не превосходит суммарную степень вершин в <tex>S</tex>. Во множестве <tex>S</tex> находится всего <tex>|S|</tex> вершин, степень каждой не превосходит <tex>k</tex>. Поэтому суммарная степень вершин в <tex>S</tex> не превосходит <tex>k|S|</tex>. Отсюда получаем неравенство:
<tex>\sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S| ~~~ \textbf{(3.1)}</tex>
