Изменения
→Трансверсальный матроид
# <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> B </tex> в синий цвет, а соответствующего <tex> A </tex> {{---}} в красный. Причем ребра, соответствующие двум паросочетаниям, будут окрашены в пурпурный цвет. Таким образом, получится <tex> \left\vert B \setminus A \right\vert </tex> ребер синего цвета, <tex> \left\vert A \setminus B \right\vert </tex> ребер красного цвета, и будет выполняться соотношение <tex> \left\vert B \setminus A \right\vert > \left\vert A \setminus B \right\vert</tex>.
#:Рассмотрим подграф <tex> H </tex>, индуцированный красными и синими ребрами из исходного графа. Каждая вершина соответствует либо двум ребрам {{---}} синему и красному, либо одному {{---}} синему или красному. Любая компонента связности представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. Так как граф двудольный, любой цикл состоит из четного числа ребер. Так как синих ребер больше, чем красных, то должен существовать путь, начинающийся и оканчивающийся синим ребром. Обозначим этот путь <tex> H' </tex>. Поменяем в <tex> H' </tex> синий и красный цвета. Получаем, что ребра, окрашенные в красный и пурпурный цвета образуют паросочетание в графе. Очевидно, что подмножество соответствующее этому новому паросочетанию имеет вид <tex>A \cup \mathcal{f} x \mathcal {g} </tex>, где <tex> x \in B \setminus A </tex>. Что значит, что <tex> A \cup \mathcal{f} x \mathcal {g} \in I</tex>.
}}
