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! 



Transversal Matroid
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.


