Изменения

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