Could I get some help for part b(i) of below please? Thanks. (Part (a) follows from Hall's Marriage Thm, and b(ii) follows quickly from b(i) I think).
Let $G$ be a bipartite graph with parts $X$ and $Y$ , and with maximum degree $r$.
(a) Let $X_0$ be the set of vertices $x$ in $X$ with degree $d(x) = r$. Show that there is a matching covering $X_0$ (that is, such that each vertex in $X_0$ is incident with an edge in the matching).
(b) Let $X_1 \subseteq X$ and $Y_1 \subseteq Y$ , and suppose that there is a matching $R$ covering $X_1$ and a matching $B$ covering $Y_1$.
- (i) Consider the subgraph containing just the edges in exactly one of $R$, $B$. Suppose that some component of this subgraph is a path with first edge in $R$ and last edge in $B$. Let $Z$ be the set of vertices in $X_1 \cup Y_1$ on the path. Show that either the edges in $R$ on the path cover $Z$, or the edges in $B$ on the path cover $Z$.
- (ii) Show that there is a matching in $G$ covering $X_1 \cup Y_1$.