137
правок
Изменения
Нет описания правки
Пусть <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>\alpha_iA_i</tex> {{---}} количество рёбер рёбра из <tex>E(G')</tex>, соединяющих соединяющие <tex>U_i</tex> с <tex>S</tex>,<tex>\alpha_i</tex> {{---}} их количество, то есть <tex>\alpha_i = |A_i|</tex>
<tex>\beta_iB_i</tex> {{---}} количество рёбер рёбра из <tex>F</tex>, соединяющих соединяющие <tex>U_i</tex> с <tex>S</tex>,<tex>\beta_i</tex> {{---}} их количество, то есть <tex>\beta_i = |B_i|</tex>
<tex>\gamma_iC_i</tex> {{---}} количество рёбер рёбра из <tex>E(G')F</tex>, соединяющих соединяющие <tex>U_i</tex> с остальными компонентами связности графа <tex>G' \setminus S</tex>,<tex>\gamma_i</tex> {{---}} их количество, то есть <tex>\gamma_i = |C_i|</tex>.
По лемме [[Совершенное паросочетание в кубическом графе#lemma1 | о сравнимости по модулю 2]] для нечётных компонент связности <tex>G' \setminus S</tex> (то есть <tex>i \in [1 \cdots n]</tex>) <tex>m_i \equiv k \pmod 2</tex>.
<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>\sum\limits_{i=1}^t \alpha_i + \sum\limits_{i=1}^t \beta_i \leqslant k|S|</tex> ~~~ \textbf{(так как у нас всего <tex>|S|</tex> вершин степени не более <tex>k3.1)}</tex>, в которые могут вести эти рёбра)
<tex>2 \sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant 2|F| \leqslant 2k - 2</tex> (так как <tex>\sum\limits_{i=1}^t \beta_i + \sum\limits_{i=1}^t \gamma_i \leqslant |F|</tex>)
