Past exam of the mathematics course of the University of Cambridge / 2006 / ii / Paper 2 / 17F / Solution

Work with finite graphs, as in the usual matching theorem. Hall's condition is $|N(A)|\ge |A|$ for every $A\subseteq X$. It is necessary because a matching injects $A$ into its neighbours.

For sufficiency, induct on $|X|$. If a nonempty proper subset $A$ has $|N(A)|=|A|$, induction matches $A$ to $N(A)$. For $B\subseteq X\setminus A$, Hall's inequality for $A\cup B$ gives $|N(B)\setminus N(A)|\ge |B|$, so induction matches the complement to unused neighbours. Combining the matchings finishes this case. Otherwise every nonempty proper $A$ has $|N(A)|\ge |A|+1$. Choose an edge $xy$, delete its endpoints, and observe that every subset of the remaining $X$ still has at least its own number of neighbours. Induction matches the remainder, and adjoining $xy$ finishes. The one-vertex case and the empty case are immediate.

For $0\le d\le |X|$, the defect version isNecessity follows because at most $d$ vertices of $X$ can be unmatched. For sufficiency add $d$ new vertices to $Y$, each joined to every vertex of $X$. The displayed inequality makes Hall's condition hold in the enlarged graph. Its full matching uses at most $d$ new vertices, giving the required original edges.

To prove the matching-cover equality, let $M$ be a maximum matching and $U$ its unmatched vertices in $X$. Follow alternating paths from $U$, using nonmatching edges from $X$ to $Y$ and matching edges back. Let $Z_X,Z_Y$ be the reachable sets. No reachable $Y$ is unmatched, since that would give an augmenting path and a larger matching. Matching edges give a bijection $Z_Y\leftrightarrow Z_X\setminus U$. The set $C=(X\setminus Z_X)\cup Z_Y$ covers every edge: an edge from a reachable $X$ to an unreachable $Y$ cannot be a nonmatching edge, and its matching edge, if present, is already reachable. Its size isEvery vertex cover has at least $|M|$ vertices, because the matching edges are disjoint. Therefore maximum matching size equals minimum vertex-cover size, as required.