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

The eigenvalues of a graph are the eigenvalues of its adjacency matrix. Order the vertices with those of $X$ first and those of $Y$ second. The adjacency matrix then has block formwhere $B$ is the $|X|\times |Y|$ bipartite adjacency matrix.

Since zero is not an eigenvalue, $A$ is invertible. If $|X|\ne |Y|$, thena contradiction. Thus $|X|=|Y|=r$. Moreover, if $B$ were singular, a nonzero $v$ with $Bv=0$ would give $A(0,v{)}^T=0$. Hence $B$ is invertible.

In the determinant expansionat least one product is nonzero. For its permutation $\pi$, all entries $B_{i,\pi (i)}$ equal one, so the corresponding $r$ edges pair every vertex of $X$ with a distinct vertex of $Y$. They form the required matching.