137
правок
Изменения
Нет описания правки
Так как <tex>|V(G)|</tex> чётно, то и <tex>odd(G' \setminus S) + |S|</tex> тоже чётно. Из этого следует, что <tex>odd(G' \setminus S) \equiv |S| \pmod 2 </tex>. Из этого факта и того, что <tex>odd(G' \setminus S) > |S|</tex> следует, что <tex>odd(G' \setminus S) \geqslant |S| + 2 ~~~ \textbf{(1)}</tex>
Пусть в графе <tex>G' \setminus S</tex> всего <tex>t</tex> компонент связности, <tex>n</tex> из которых нечётны. Тогда пусть <tex>U_1, \cdots, U_n</tex> {{---}} нечётные компоненты связности <tex>G' \setminus S</tex>, тогда <tex>|odd(G' \setminus S)| = n</tex>, а <tex>U_{n+1}, \cdots, U_t</tex> {{---}} его чётные компоненты связности. Для каждого <tex>i \in [1 \cdots t]</tex> определим три величины:
<tex>A_i</tex> {{---}} рёбра из <tex>E(G')</tex>, соединяющие <tex>U_i</tex> с <tex>S</tex>, <tex>\alpha_i</tex> {{---}} их количество, то есть <tex>\alpha_i = |A_i|</tex>
<tex>\sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S| ~~~ \textbf{(3.1)}</tex>
Заметим, что множества рёбер <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>2 \sum\limits_{i=1}^t \beta_i |B_i| + \sum\limits_{i=1}^t \gamma_i \leqslant 2|FC_i| \leqslant 2k - 2</tex> (так как <tex>= \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant |</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.1)}</tex> (так как <tex>|F| \leqslant k - 1</tex>) Сложив которые<tex>\textbf{(3.1)}</tex> и <tex>\textbf{(3.2)}</tex>, получаем
<tex>\sum\limits_{i=1}^t \alpha_i + 3\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^n \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}</tex>
