Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 17F / a / i / Solution

Let the bipartition be $X\bigsqcup Y$. Counting edges from each side givesso $|X|=|Y|=n/2$. For $S\subseteq X$, the $k|S|$ edges leaving $S$ all end in $N(S)$, while each vertex of $N(S)$ receives at most $k$ of them. Thereforeand Hall's condition holds. There is a matching covering $X$, of size $n/2$. No matching can use more than one edge at each vertex, so this is maximal and