= Solution
{c}
By part (i), choose a <matching in a graph> $M_1$ meeting all <vertices> of <vertex degree> $\Delta$ in $A$. Interchanging the two <vertex sets> gives a <matching in a graph> $M_2$ meeting all such <vertices> in $B$. Consider the spanning <subgraph> $H$ with <edges> $M_1\cup M_2$.
Every <vertex> has <vertex degree> at most two in $H$. An <edge> belonging to both <matchings in a graph> forms a whole two-<vertex> <connected component of a graph>, since neither endpoint can meet another <edge> of either <matching in a graph>. On every other nontrivial <connected component of a graph>, the <edges> alternate between $M_1$ and $M_2$, so the <connected component of a graph> is a <graph path> or an even <graph cycle>. We select one of the two <matchings in a graph> separately on each <connected component of a graph>.
On a <graph cycle>, either choice covers every <vertex>. On a <graph path> with an odd number of <edges>, the first and last <edges> belong to the same <matching in a graph>; choose it, and it covers every <vertex> of the <graph path>. For a common <edge>, choose that <edge>.
It remains to treat a <graph path> with a positive even number of <edges>. Its endpoints lie in the same side of the <bipartite graph>. Every internal <vertex> meets both <matchings in a graph>. If both endpoints lie in $A$, choose $M_1$: every endpoint of <vertex degree> $\Delta$ must already be met by $M_1$, by its defining property. If both endpoints lie in $B$, choose $M_2$ for the same reason. Thus the choice meets all <vertices> of <vertex degree> $\Delta$ in that <connected component of a graph>.
Finally, an isolated <vertex> of $H$ cannot have <vertex degree> $\Delta$ in $G$, since it would have been met by $M_1$ or $M_2$. The union of the selected <edges> over the <connected components of a graph> is a <matching in a graph>, because different <connected components of a graph> have disjoint <vertex sets>. It meets every <vertex> of <vertex degree> $\Delta$ in $G$. The useful mechanism is the <union of two matchings> and its alternating <connected components of a graph>.
Back to article page
