137
правок
Изменения
Нет описания правки
<tex>m_i \geqslant \lambda(G) \geqslant k - 1</tex>. Из этого факта и того, что <tex>m_i \equiv k \pmod 2</tex> следует, что <tex>m_i \geqslant k</tex>. Отсюда получаем неравенство:
<tex>\sum\limits_{i=1}^n m_i = \sum\limits_{i=1}^n (\alpha_i + \beta_i + \gamma_i) = \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>. Отсюда получаем неравенство:
