Past exam of the mathematics course of the University of Cambridge / 2011 / ii / Paper 1 / 17F (Graph Theory)

A matching in a graph is a set of edges with no shared endpoints. A matching from $X$ to $Y$ here covers every vertex of $X$. Necessity of the Hall marriage theorem condition is immediate: the partners of vertices of $A\subseteq X$ are distinct members of its neighbour set $\Gamma (A)$.

For sufficiency, take a matching of maximum size. If it leaves $x\in X$ unmatched, follow alternating unmatched and matched edges from $x$. Let $A\subseteq X$ and $B\subseteq Y$ be the reachable vertices. No vertex of $B$ can be unmatched, because the resulting augmenting path in a matching would increase the matching. Every neighbour of $A$ is in $B$, and the matching pairs $B$ bijectively with $A\setminus \{x\}$. Thus $|\Gamma (A)|=|B|=|A|-1$, contradicting Hall's condition. The maximum matching therefore covers $X$.

For the deficiency bound, adjoin $d$ new vertices to $Y$, each adjacent to all of $X$. Every nonempty $A$ then has $|\Gamma (A)|+d\ge |A|$ neighbours. Apply the Hall marriage theorem and remove the at most $d$ edges using new vertices. This leaves at least $|X|-d$ independent edges. The lower bound is vacuous if $d>|X|$.

Write the adjacency matrix of a graph in bipartite block form $\left(\begin{array}{cc}0& C\\ C^T& 0\end{array}\right)$. If Hall's condition failed for $A\subseteq X$, the linear map from vectors supported on $A$ to their neighbour coordinates in $Y$ would have fewer output than input coordinates. It therefore has a nonzero kernel, giving a nonzero vector $v$ supported on $A$ with $C^{T}v=0$. The vector $(v,0)$ would be a zero eigenvector of the adjacency matrix. Consequently absence of the zero eigenvalue implies a matching covering $X$.

The converse is false, even with equal part sizes. The four-cycle $K_{2,2}$ has a perfect matching, but its matrix $C=\left(\begin{array}{cc}1& 1\\ 1& 1\end{array}\right)$ is singular. Its adjacency matrix has eigenvalues $2,-2,0,0$.