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

A matching in a graph from $X$ to $Y$ chooses one distinct neighbour in $Y$ for each vertex of $X$. For a finite bipartite graph, the Hall marriage theorem states that such a matching exists if and only if $|\Gamma (A)|\ge |A|$ for every $A\subseteq X$. Necessity follows because the matched neighbours of $A$ are distinct members of $\Gamma (A)$.

For sufficiency use induction on $|X|$, with the empty and one-vertex cases immediate. If some nonempty proper $A$ satisfies $|\Gamma (A)|=|A|$, the induced graph on $A,\Gamma (A)$ satisfies Hall's condition. The remaining graph on $X\setminus A,Y\setminus \Gamma (A)$ does too: for $B\subseteq X\setminus A$,Inductively match both pieces and combine them. If no nonempty proper subset is tight, choose an edge $xy$ and remove its endpoints. Every nonempty subset $B$ of the remaining $X$ is proper in the original $X$, so $|\Gamma (B)|\ge |B|+1$; removing $y$ preserves Hall's condition. Match the remainder inductively and add $xy$. This proves the theorem without a flow or disjoint-path theorem.

Fix any edge $xy$. After deleting $x$ and $y$, every nonempty subset $A$ of $X\setminus \{x\}$ satisfies $|\Gamma (A)\setminus \{y\}|\ge |A|$, by the strict inequality in the question. The Hall marriage theorem gives a matching in a graph for the remainder; adding $xy$ gives a matching covering $X$ and containing the prescribed edge. The case $|X|=1$ is immediate.

Suppose a nonempty proper $A$ is tight. In every matching in a graph covering $X$, the vertices of $A$ use every vertex of $\Gamma (A)$. Hence no edge from $X\setminus A$ to $\Gamma (A)$ could occur in such a matching. The assumption that every edge occurs therefore rules out all such edges. By definition there are also no edges from $A$ to $Y\setminus \Gamma (A)$. This separates $A\cup \Gamma (A)$ from the rest, which contains the nonempty set $X\setminus A$, contradicting connectedness. Hall's inequality must therefore be strict on every nonempty proper $A$.

Take a disjoint union of $n$ single edges, each joining one vertex of $X$ to one of $Y$. Its unique matching in a graph covering $X$ contains every edge, while any singleton $A\subset X$ satisfies $|\Gamma (A)|=|A|=1$. For $n\ge 2$ this $A$ is nonempty and proper. This illustrates why connectedness was needed in part (ii).

No. In the six-cycle with cyclic vertices $1,2,\dots ,6$, every edge belongs to one of the two alternating perfect matchings. However, the disjoint edges $12$ and $45$ cannot belong to a common perfect matching: the remaining vertices $3,6$ are not adjacent. Taking $X=\{1,3,5\}$ and $Y=\{2,4,6\}$ gives the required bipartite graph counterexample.