Изменения

Так как <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>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_1^n \alpha_i + \sum\limits_1^n \beta_i + \sum\limits_1^n \gamma_i \geqslant kn ~~~ \textbf{(2)}</tex> Отметим два неравенства: <tex>\sum\limits_1^t \alpha_i + \sum\limits_1^t \beta_i \leqslant k|S|</tex> <tex>2 \sum\limits_1^t \beta_i + \sum\limits_1^t \gamma_i \leqslant 2|F| \leqslant 2k - 2</tex> Сложив которые, получаем <tex>\sum\limits_1^t \alpha_i + 3\sum\limits_1^t \beta_i + \sum\limits_1^n \gamma_i \leqslant k(|S| + 2) - 2 ~~~ \textbf{(3)}</tex> Из неравенств <tex>\textbf{(2)}</tex> и <tex>\textbf{(3)}</tex> получаем, что <tex>kn \leqslant k(|S| + 2) - 2</tex>, и, следовательно, <tex>odd(G' \setminus S) = n < |S| + 2</tex>, что противоречит <tex>\textbf{(1)}</tex>. Таким образом, множество Татта найти нельзя, значит, в <tex>G'</tex> существует совершенное паросочетание.