= Solution
{c}
Let $A_\Delta=\{a\in A:d_G(a)=\Delta\}$. Apply <Hall's marriage theorem> to the <induced subgraph> on $A_\Delta\cup B$, which is a <bipartite graph>. For any <subset> $S\subseteq A_\Delta$, <double counting> the <edges> from $S$ to its <graph neighbourhood> gives
$$
\Delta|S|=\sum_{a\in S}d_G(a)=e_G(S,N(S))
\leq\sum_{b\in N(S)}d_G(b)\leq\Delta|N(S)|.
$$
The equality uses the fact that every <neighbour> of $S$ lies in $B$, so all <edges> incident with $S$ have been counted. The final inequality uses the <maximum degree> bound on $B$. Since $\Delta>0$, division gives the <Hall condition> $|S|\leq|N(S)|$.
Consequently there is a <matching in a graph> $M_1$ saturating $A_\Delta$. If $A_\Delta$ is empty, use the empty <matching in a graph>. This proves the required <matching covering maximum-degree vertices in a bipartite graph> on the specified side; other <vertices> need not be met.
Back to article page
