= Solution
{c}
We verify the <Hall condition> for $U$. Let $S\subseteq U$. If $S$ is empty, then $|N(S)|=0=|S|$. Suppose $0<|S|\leq n/2$. Choose $u\in S$. Its <graph neighbourhood> is contained in $N(S)$, so the <minimum degree> hypothesis gives
$$
|N(S)|\geq d_G(u)\geq n/2\geq|S|.
$$
If $|S|>n/2$, suppose for a contradiction that some <vertex> $w\in W\setminus N(S)$ exists. All <neighbours> of $w$ lie in $U\setminus S$, so
$$
d_G(w)\leq n-|S|<n/2,
$$
contradicting the <minimum degree> hypothesis. Thus $N(S)=W$ and $|N(S)|=n\geq|S|$.
Every <subset> $S\subseteq U$ satisfies the <Hall condition>. By <Hall's marriage theorem>, there is a <matching in a graph> saturating $U$. Since $|U|=|W|=n$, its $n$ <edges> also cover every <vertex> of $W$. It is therefore a \b[complete matching], meaning a <perfect matching>. For $n=0$, the empty <matching in a graph> already has this property.
Back to article page
