Let $G$ be a bipartite graph with parts $A$ and $B$. Let $U\subseteq A$ and $V\subseteq B$ and assume that there exists matching in $G$ that covers all vertices in $U$ and another matching that covers all vertices in $V$. Show that there is a matching that covers all vertices in $U \cup V$. (Hint: consider the union of these two matchings - how does it look like?)
Here is my attempt:
Let $M_1$ be the matching that covers all vertices in $U$ and similarly let $M_2$ be the matching for $V$. Let $M=M_1 \cup M_2$. We need to show that it is possible for $M$ to be a matching that covers the union of $U$ and $V$. Now $M$ would clearly cover all vertices in $U$ and $V$ (should I explain this more) but it might not be a matching because it might have edges that have vertices in common. If $M$ has no edges that contains vertices in common, then we are done so $M$ would be a matching of what we need to show which is described in the question. Assume that this is not the case. Note that for all edges say $uv$ contained $G$, vertex $u \in A$ and vertex $v \in B$, otherwise it wouldn't be a bipartite graph. Let us consider three arbitrary vertices in $G$, say $u\in U$ and $v,p \in V$. Let $uv, up \in M$. Having these two edges would mean that $M$ is not a matching because there is a vertex in common which is $u$. We should note that these two edges cannot be both in $M_1$ or both in $M_2$ otherwise $M_1$ and $M_2$ would not be matching sets. So lets say without loss of generality that $uv \in M_1$ and $up \in M_2$. We can delete edge $uv$ because vertex $v$ will already be covered in $M$ because vertex $v$ will be in $M_2$ - otherwise $M_2$ would not cover all vertices in $V$ since $v \in V$. Since our vertices were arbitrary, after the necessary deletions, $M$ will be a matching that covers all vertices in $U \cup V$.
Please tell me anything at all wrong with it or where it needs more justification. I might have jumped a bit in the last part. I would want to see how this is best answered.
Here's a solution which makes use of the hint. Think of $M=M_1\cup M_2$ (where $M_1$ is the matching that covers $U$, and $M_2$ is the matching that covers $V$) as a directed graph; edges in $M_1$ are directed from $A$ towards $B$ ("red"), and edges in $M_2$ are directed the other way ("blue"). Every vertex in $M$ has degree $1$ or $2$, so the components of $M$ are either simple paths or cycles. Furthermore, the degree-$2$ vertices have one incoming edge and one outgoing edge, so the paths and cycles are directed paths and directed cycles whose edges alternate red and blue. Note that since vertices in $U\cup V$ have an outgoing edge, a component of $M$ which is a path cannot end in either $U$ or $V$.
We now select edges from $M$ to obtain a matching. For each path, select alternating edges starting with the first. If the path has an odd number of edges (hence covers an even number of points) this is a matching between the $A$ points on the path and the $B$ points. If there's an extra edge, we don't cover the last vertex - but that vertex is neither in $U$ nor $V$ so that's OK. For each cycle, select alternating edges starting anywhere you like (i.e. take either the red edges or the blue edges). In either case, you get a matching which covers all the vertices in the cycle. The resulting matching covers all the vertices in $M$ except for some path endpoints, which were not in $U$ or $V$, hence the matching covers $U\cup V$.$\ \square$
We remark that in the special case that we started with a matching $M_1$ from $U$ into $B$, and a matching $M_2$ from $V$ into $A$, this argument shows that $M$ contains exactly $2^k$ matchings covering $U\cup V$, where $k$ is the number of cycles in $M$.