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

Hall's marriage theorem states that a finite bipartite graph with parts $A,B$ has a matching in a graph saturating $A$ exactly when $|N(S)|\ge |S|$ for every $S\subseteq A$. Necessity follows because the matched neighbours of $S$ are distinct.

For sufficiency use induction on $|A|$. The empty case is immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, the induced graph on $S,N(S)$ satisfies Hall's condition and has a saturating matching in a graph by induction. The remaining graph on $A\setminus S,B\setminus N(S)$ also satisfies it: for $T\subseteq A\setminus S$,Apply induction again and unite the two matchings in a graph. If there is no such tight proper subset, every nonempty proper $S$ has $|N(S)|\ge |S|+1$. Choose a vertex $a$ and a neighbour $b$, which exists by Hall's condition. Delete both. Every remaining subset loses at most one neighbour and still satisfies Hall's condition. Induction supplies a matching in a graph of the remainder; add $ab$. For $|A|=1$ this last step directly proves the assertion.

Let $A,B$ be the two parts of the bipartite graph. Counting edges gives $k|A|=k|B|$, hence $|A|=|B|=n/2$. For $S\subseteq A$, the $k|S|$ edges incident to $S$ all end in $N(S)$, whose vertices have total capacity $k|N(S)|$. Thus $|N(S)|\ge |S|$. Hall's marriage theorem gives a perfect matching, and no matching in a graph can have more than $n/2$ edges. The matching number is $\boxed{n/2}$.

Take a maximal matching in a graph with $m$ edges and let $S$ be its $2m$ endpoints. Maximality makes its complement an independent set, since an edge wholly outside $S$ could be added. Every vertex outside $S$ therefore sends all its $k$ edges into $S$, giving $k(n-2m)$ crossing edges. Every vertex in $S$ already uses at least one incident edge inside $S$, its matched edge, so it sends at most $k-1$ outside. HenceThe maximum matching in a graph is at least this large. For $k=2$, take any disjoint union of $r$ triangles. It is 2-regular, has $n=3r$ vertices and matching number $r=n/3$, since each triangle contributes exactly one edge. As $r$ varies this gives infinitely many equality examples.