Изменения

Тогда <tex>G</tex> имеет совершенное паросочетание тогда и только тогда, когда <tex>\forall S \supseteq L : |S| \leq r(S)</tex>.

1. <tex>\forall S \supseteq L (, |S| \neq 0)</tex> строго расширяется, то есть <tex>|r(S)| > |S|</tex>. <tex>\measuredangle \ \ \forall x \supset V(L) : (x, y) \in E</tex>. <tex>\measuredangle G^{*} : L^{*} = L \diagdown {x}</tex> и <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S \supset L</tex> строгому неравенству теоремы, каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, так как только одна вершина <tex>y</tex> удалена из <tex>R</tex> следовательно по предположению индукции меньший граф <tex>G^{*}</tex> имеет паросочетание. К этому паросочетанию добавляем ребро {x, y} что дает совершенное паросочетание.

2. Пусть Выберем <tex>\exists T forall x \supset V(L) : (x, y) \in E</tex>. Тогда рассмотрим двудольный граф <tex>G^{*}</tex>, у которого левая доля <tex>L^{*} = L \ (|T| diagdown {x}</tex>, а правая <tex>R^{*} = R \diagdown {y}</tex>. Так как <tex>\forall S \neq 0)supset L</tex> удовлетворяет строгому неравенству теоремы, то каждое подмножество <tex>L^{*}</tex> удовлетворяет неравенству, поскольку только одна вершина <tex>y</tex> была удалена из <tex>R</tex> такое. Следовательно, что по предположению индукции меньший граф <tex>|r(T)| = |T|G^{*}</tex>имеет паросочетание. К этому паросочетанию добавляем ребро (x, y) что дает совершенное паросочетание.

2. Пусть <tex>\measuredangle</tex> порожденные графы <tex>G_{1} = exists\ T \bigcup r(in L, \ |T)| \neq 0</tex> и такое, что <tex>G_{2} = L \diagdown T \bigcup R \diagdown |r(T)| = |T|</tex>.

<tex>\measuredangle</tex> порожденные графы <tex>G_{1} = T \cup r(T)</tex> и <tex>G_{2} = L \diagdown T \cup R \diagdown r(T)</tex>. По предположению индукции <tex>G_{1}</tex> имеет совершенное паросочетание (Заметим, что предположение индукции не может использоваться использовано непосредственно на <tex>G_{2}</tex>).

<tex> r_{G_{2}}(S) = r_{G}(S \bigcup cup T) \diagdown r_{G}(T) \ \Rightarrow</tex> <tex>|r_{G_{2}}| \geqslant |S \bigcup cup T| - |T| = |S|</tex>

Неравенство верно, поскольку <tex>S \bigcup cup T</tex> удовлетворяет <tex>|r_{G}(S \bigcup cup T)| \geqslant |S \bigcup cup T|</tex> и по предположению индукции <tex>|r_{G}(T)| = |T|</tex>.

Следовательно, <tex>G_{2}</tex> также удовлетворяет неравенству теоремы и по предположению индукции имеет паросочетание. Объединение совершенных паросочетаний <tex>G_{1}</tex> и <tex>G_{2}</tex> {{---}} паросочетание для <tex>G</tex>.