Изменения

<tex>r_2 (S \setminus U) \le |J \cap (S \setminus U)|</tex>

|proof =

От противного. Пусть <tex>\exists z \in (S \setminus U) \setminus J</tex> : <tex>J \cap (S \setminus U) + z \in I_2</tex>. Аналогично доказательству предыдущего утверждения, <tex>\exists y \in J \setminus (S \setminus U)</tex> : <tex>J - y + z \in I_2</tex>. Однако <tex>J \setminus (S \setminus U) = J \cap U</tex>, то есть <tex>(z, y)</tex> - дуга в <tex>D_{M_1, M_2}(J)</tex>, поэтому <tex>z \in U</tex> (т.к. <tex>y \in U</tex>). Противоречие.

}}

<tex>J' = J \bigtriangleup V(P) \in I_1 \cap I_2</tex>

|proof =

Пусть <tex>P = z_0, y_1, z_1, ..., y_t, z_t</tex>, <tex>G = \{ z_1, ..., z_t \} \cup (J \setminus \{ y_1, ..., y_t \})</tex>. Тогда <tex>G \subseteq S</tex>, <tex>|G| = |J|</tex> и дуги из <tex>\{ y_1, ..., y_t \}</tex> в

<tex>\{ z_1, ..., z_t \}</tex> составляют единственное полное паросочетание в <tex>J \bigtriangleup G</tex>. То есть, согласно [[Лемма о единственном паросочетании в графе замен | лемме о единственном паросочетании в подграфе замен]], <tex>G \in I_1</tex>.