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>
