= Solution
<Hall's marriage theorem> says that a <bipartite graph> with parts $L,R$ has a <matching> saturating $L$ if and only if
$$
\boxed{|N(S)|\geq|S|\qquad\text{for every }S\subseteq L.}
$$
Necessity follows because the matched <neighbours> of <vertices> of $S$ are distinct and belong to $N(S)$.
For sufficiency, assume these <inequalities>. Let $K=U\cup W$ be any <vertex cover>, with $U\subseteq L$ and $W\subseteq R$. Every <neighbour> of $S=L\setminus U$ must belong to $W$, since otherwise its <edge> from $S$ is uncovered. Therefore $|W|\geq|N(S)|\geq|S|$, and $|K|\geq|U|+|S|=|L|$. The whole part $L$ is itself a <vertex cover> of size $|L|$. Part (ii) now gives a <matching> of size exactly $|L|$, so it saturates $L$.
Back to article page
