92
правки
Изменения
м
Нет описания правки
Пусть <tex>S \supseteq L \diagdown T</tex>, тогда:
<tex> r_\Gamma_{G_{2}}(S) = r_\Gamma_{G}(S \cup T) \diagdown r_\Gamma_{G}(T) \ \Rightarrow</tex> <tex>|r_\Gamma_{G_{2}}| \geqslant |S \cup T| - |T| = |S|</tex>
Неравенство верно, поскольку <tex>S \cup T</tex> удовлетворяет <tex>|r_\Gamma_{G}(S \cup T)| \geqslant |S \cup T|</tex> и по предположению <tex>|r_\Gamma_{G}(T)| = |T|</tex>.
Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.
