137
правок
Изменения
Нет описания правки
Заметим, что множества рёбер <tex>B_i</tex> и <tex>C_j</tex>, не пересекаются, так как <tex>B_i</tex> ведут из <tex>U_i</tex> в <tex>S</tex>, а <tex>C_j</tex> ведут из <tex>U_j</tex> в <tex>U_k</tex>, (<tex>k \neq j</tex>). Так как <tex>B_i \subset F</tex> и <tex>C_j \subset F</tex>, то сумма <tex>\sum\limits_{i=1}^t |B_i| + \sum\limits_{i=1}^t |C_i| = \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i</tex> не превосходит мощности <tex>F</tex>, откуда имеем:
<tex>2 \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant 2|F| \leqslant 2k - 2 ~~~ \textbf{(3.12)}</tex> (так как <tex>|F| \leqslant k - 1</tex>)
Сложив <tex>\textbf{(3.1)}</tex> и <tex>\textbf{(3.2)}</tex>, получаем
