∆(G) = the maximum degree of the graph, (not sure how common the notation is)
I initially misread this and thought it was perfect matchings. But now that I see it's just plain old matchings, I'm still not sure how to start.
I was thinking of arguing that we could 1st take a matching using 1 edge from the vertex v which has the maximum degree and all other edges except those incident to v.
Then add successive matchings by adding unused edges at are incident to v.
This would give me ∆(G) matchings since there are ∆(G) edges from v, but I don't know the justification, or if I need to mention properties of bipartite graphs
Best Answer
First, following Bob Krueger’s comment, assume that the graph $G$ is regular. For this case we shall prove the requested claim by the induction with respect to $\Delta(G)$. If $\Delta(G)=0$ then the claim is trivially positive. Now assume that we already have proved the claim when $\Delta(G)=k$ and assume that $\Delta(G)=k+1$. We claim that the graph $G$ satisfies the condition of Hall's marriage theorem. Let $W$ be an arbitrary subset of $X$. Consider an induced subgraph $H$ of $G$ with the vertex set $W\cup N_G(W)$. The average degree of a vertex of $W$ is $\Delta(G)$, so the average degree of a vertex of $N_G(W)$ is $\Delta(G)\cdot |W|/|N_G(W)|\le \Delta(G)$, because $\Delta(G)$ is the maximum degree of a vertex of $G$ and so of $N_G(W)$ too. The inequality implies $|W|\le |N_G(W)|$. Thus the graph $G$ satisfies the condition of Hall’s theorem. Then it contains a perfect matching $M$. Removing $M$ from the edgeset of $G$ we obtain a regular graph with (maximum) vertex degree $\Delta(G)-1=k$, which by the induction hypothesis is a union of $k$ matchings. Adding $M$ to this union, we obtain a representation of the edgeset of the graph $G$ as a union of $k+1=\Delta(G)$ matchings, Q.E.D.
Now it remains to we reduce the problem to the regular case. The way to the reduction is to add edges to $G$ keeping its bipartiteness and maximum degree until we obtain a regular graph. So it remains to show that if $G$ is a not regular then there exist vertices $v$ and $u$ of its different color classes such that both their degrees are less than $\Delta(G)$. If this is not a case then the vertices of one of the color classes all have maximum degree $\Delta(G)$. Then $\Delta(G)$ is the average degree of the vertex of the other color class, so all vertices of this class have degree $\Delta(G)$, and this proves the regularity of $G$.