Изменения
Нет описания правки
{{Утверждение
|statement =
<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 \cap U| + |J \setminus U| \ge r_1 (U) + r_2 (S \setminus U)</tex>, <tex>|J| = r_1 (U) + r_2 (S \setminus U)</tex>. Таким образом, <tex>J</tex> - максимальное по мощности независимое множество в пересечении <tex>M_1</tex> и <tex>M_2</tex>.
