Изменения
→Матроид паросочетаний
# <tex>A \subset B, \ B \in I \Rightarrow A \in I</tex>
#:Удалим из исходного паросочетания <tex>P</tex> ребра, концами которых являются вершины из множества <tex>B \setminus A</tex>. Оставшееся множество ребер будет являться паросочетанием, покрывающим <tex>A</tex>. Значит <tex>A \in I</tex>.
# <tex>A \in I, \ B \in I, \ \left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \mathcal {9} exists ~ x \in B \setminus A, \ A \cup \mathcal{f} x \mathcal {g} \in I</tex>
#:Пусть паросочетание <tex>P_A</tex> покрывает множество <tex>A</tex>, <tex>P_B</tex> {{---}} множество <tex>B</tex>.
#:Все вершины, принадлежащие <tex>A \cap B</tex> покроем ребрами из паросочетания <tex>P_B</tex>.
#:Так как <tex>\left\vert A \right\vert < \left\vert B \right\vert \Rightarrow \exists x \in B \setminus A</tex>
#:Рассмотрим три возможных случая:
## <tex>\exists xy \in P_A, \ y \in A \Rightarrow P_A</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal {g} \in I</tex>## <tex>\exists xy: y \in B \setminus A \Rightarrow xy \notin P_A</tex>. Мы можем добавить в <tex>A</tex> вершину <tex>x</tex> (или <tex>y</tex>), а в <tex>P_A</tex> ребро <tex>xy</tex>. Тогда паросочетание <tex>P_A \cup xy</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal{g} \in I</tex>## Если первые два случая не выполнились, значит <tex>\forall x \in B \setminus A</tex> <tex>\exists y \notin A, \ \notin B: \exists xy \in P_B</tex>. Обозначим множество таких <tex>y</tex> за <tex>C, \ \left\vert C \right\vert = \left\vert B \setminus A \right\vert > \left\vert A \setminus B \right\vert</tex>. Таким образом в <tex>C</tex> найдется хотя бы одна вершина <tex>y</tex>, не покрытая паросочетанием <tex>P_A</tex>. Тогда паросочетание <tex>P_A \cup xy</tex> покрывает <tex>A \cup \mathcal{f} x \mathcal {g} \Rightarrow A \cup \mathcal{f} x \mathcal{g} \in I</tex>
}}
