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

A matching from $X$ to $Y$ is a set of pairwise vertex-disjoint edges that covers every vertex of $X$. Equivalently, it chooses for each $x\in X$ a distinct neighbour in $Y$.

Hall marriage theorem says that such a matching exists if and only ifNecessity is immediate: the distinct partners of the vertices in $S$ all belong to $N(S)$.

For sufficiency, induct on $|X|$. The claim is clear when $|X|=1$. First suppose every nonempty proper $S\subset X$ satisfies the strict inequality $|N(S)|\ge |S|+1$. Choose an edge $xy$ and delete $x$ and $y$. For $S\subseteq X\setminus \{x\}$, deletion removes at most one neighbour, soInduction gives a matching of $X\setminus \{x\}$, and adding $xy$ completes it.

Otherwise there is a nonempty proper $S\subset X$ with $|N(S)|=|S|$. Hall's condition holds in the bipartite graph induced by $S\cup N(S)$, so induction matches $S$ onto $N(S)$. For $A\subseteq X\setminus S$,and hence $A$ has at least $|A|$ neighbours outside $N(S)$. Induction therefore matches $X\setminus S$ into $Y\setminus N(S)$. The two matchings are disjoint and together cover $X$.

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

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

For every $r\ge 1$, take the disjoint unionof $r$ triangles. This graph is $2$-regular, has $n=3r$ vertices, and each triangle contributes exactly one edge to a maximum matching. Henceso equality holds for this infinite family.

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.