# Transversal Matroid

I am trying to figure out why the transversal matroid is a matroid. Specifically, if $L$ and $M$ are two independent sets s.t. $|L| < |M|$, why is there an $i$ in $M \setminus L$ s.t. $L \cup \{ i \}$ is independent? thank you in advance!

Let me check that we have the same definition of transversal matroids. For me, the input is a bipartite graph $\Gamma$, with white vertex set $W$ and black vertex set $B$. The ground set of the matroid is $B$, with a subset of $B$ being independent if it can be matched to a subset of $W$.
Direct Proof that this is a matroid: Suppose that $M$ and $L$ are subsets of $B$ can be matched, with $|L|<|M|$. Superimpose the matchings. This gives a graph $G$ where the elements each vertex has degree $\leq 2$ -- so a union of paths and cycles (including possibly some $2$ cycles.) We'll call an edge of $G$ mauve or lavender acording to whether it comes from $M$ or $L$. In each path or cycle of $G$, the edges alternate color.
Each element of $M \setminus L$ gives a degree $1$ in $B$ at the end of a mauve edge, and each element of $L \setminus M$ gives a degree one element of $B$ at the end of a lavender edge. Since $|M| > |L|$, there must be a path one of whose ends is a mauve edge ending in $W$ and whose other end is not a lavender edge ending in $B$. The only other possibility for the end of that path is a mauve edge ending in $W$. In other words, this path has vertices $b_1$, $w_1$, $b_2$, $w_2$, ..., $b_r$, $w_r$ where $b_i$ is matched to $w_i$ in $M$, $w_i$ is matched to $b_{i+1}$ in $L$ and $b_1$ and $w_r$ are not matched in $L$. Now modify $L$ to match $b_i$ to $w_i$, leaving all other elements of $L$ matched as before. This is a matching of $L \cup \{ b_1 \}$.
Conceptual proof Take a matrix $A$ with rows labeled by $W$ and columns labeled by $B$. Place a $0$ in $A_{bw}$ if $\Gamma$ has no edge between $b$ and $w$, and place algebraically independent elements in the positions where $\Gamma$ does have an edge. The transversal matroid is realized by the columns of this matrix.