Vertices of Matchings in bipartite Graph are Matroid

Question

Let $G=(V,E)$ be a bipartite graph with $V=A \cup B$ (disjoint) and $\mathcal{F}=\{V(N) \cap B\ |\ N\ is \ a\ matching\ in\ G\}$ . Now I have to prove that $(B,\mathcal{F})$ is a matroid. The first two properties are obvious (you can use an empty matching and therefore $\emptyset \in \mathcal{F}$, if $F\subseteq F'$ and $F' \in\mathcal{F}$ then there is of course a matching so that $F\in \mathcal{F}$) but I don't know how to prove the exchange property. Could anyone please help me? Thanks!

Answer 1

Let $C,D\in \mathcal{F}$ with $|C|<|D|$. We need to show there exists $d\in D$ such that $C+d\in \mathcal{F}$.

Consider $N_C$ and $N_D$ matchings of $G$ such that their intersection with $B$ are $C$ and $D$ respectively. We will now do a standard trick in matching theory: consider the graph $G'$ induced by $N_C\cup N_D$; this graph has maximum degree two, and thus is a union of (alternating) paths and cycles. Since $G$ is bipartite, all cycles in $G'$ are even. Since $|D|>|C|$, there exists a path $P$ in $G'$ with an odd number of edges, and with more edges in $N_D$ than in $N_C$. Thus, the first and last edge (which could be the same edge if $P$ has one edge) are in $N_D$. Thus $P$ is an $N_C$ augmenting path, i.e., $N:=N_C\Delta E(P)$ is a matching of larger size. Thus, $|V(N)\cap B|>|C|$, and since the added edges have ends in $D$, we are done.