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

Let $M$ be a maximum matching and put $m=|M|$. The $n-2m$ unmatched vertices form an independent set, since an edge between two of them could be added to $M$. Because $G$ is $k$-regular, exactly $k(n-2m)$ edges run from unmatched vertices to vertices covered by $M$.

Each endpoint of a matched edge has one incident edge in $M$, and hence at most $k-1$ incident edges from unmatched vertices. The two endpoints of each of the $m$ matched edges therefore receive at most $2k-2$ such edges. ThusRearranging gives

Solved by gpt-5.6-sol high.