Why does the result follow from the proof that has been given? I read this post: https://mathoverflow.net/questions/219909/a-matching-that-covers-vertices-with-maximum-degree
The general idea is to add vertices such that the edges of the new graph are the edges of the old graph joined with the edges that we obtain by joining all vertices of $W$ and joining all those of $W$ with the vertices of $U$. Then one shows that this graph has a perfect matching using Tutte's theorem. However, how does it follow that $G(M)$, assuming it is bipartite, has a matching that covers all of $M$? Thanks in advance for any help!
 A: A general statement of the technique we're using here is:

Let $G$ be a graph and let $S \subseteq V(G)$ be any set of vertices. Let $H$ be a supergraph of $G$ such that for all $v\in S$, $\deg_G(v) = \deg_H(v)$: $H$ has no edges incident to $v$ that are not also in $G$. Then if $H$ has a perfect matching, $G$ has a matching that covers all of $S$.

Proof. Take a perfect matching in $H$ and throw away all its edges that are not edges of $G$. This does not throw away any edges incident to a vertex in $S$, therefore all such vertices remain covered. $\square$

In the construction from the MathOverflow post, what we're doing fits into this framework:

*

*$S \subseteq V(G)$ (called $M$ in that post) is the set of all vertices of degree $\Delta$.

*$H$ is constructed from $G$ by adding new vertices adjacent to each other and to all vertices not in $S$: therefore $\deg_G(v) = \deg_H(v) = \Delta$ for all $v \in S$.

Therefore finding a perfect matching in the bigger graph $H$ is enough to find a matching in $G$ that covers all vertices of degree $\Delta$.
The weaker statement "If $G$ is a bipartite graph with maximum degree $\Delta$, then it has a matching covering all vertices of degree $\Delta$" is well-known and also proven using this technique. The procedure there is:

*

*If necessary, add isolated vertices to one side of the bipartition to make the number of vertices on both sides equal.

*Arbitrarily add edges (respecting the bipartition) between vertices of degree less than $\Delta$ until the graph is $\Delta$-regular. (We may end up with a multigraph at this stage; that's fine.)

*Apply Hall's theorem to show that any $\Delta$-regular bipartite multigraph has a perfect matching.

*Take all edges of the perfect matching that exist in the original graph $G$, and we cover all vertices of degree $\Delta$.

