# Algorithm for bipartite graph

I need an algorithm for finding in a bipartite graph a matching saturating all vertices of maximum degree. How do I come up with such an algorithm?

-

The non-trivial part of this question is to prove the existence of such a matching. Let $G$ be a bipartite graph $G$ with max-degree $\Delta$, and let $S$ be the set of vertices of degree $\Delta$. Create a bipartite $\Delta$-regular graph $G'$ from $G$ by adding "dummy" edges (and also dummy vertices, if necessary, to make the graph balanced). The key claim is that all edges in $G'$ that are incident on $S$ are non-dummy edges, and it isn't hard to see why (Exercise!).
By Hall's theorem for regular bipartite graphs, $H$ has a perfect matching, say $M'$. Now, simply delete the dummy edges from $M'$ to get the matching $M$. From the key claim above, it follows that $M$ is indeed a matching in $G$ and it saturates all of $S$.