Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 17G / Solution

Hall marriage theorem states that a bipartite graph with parts $A,B$ has a matching saturating $A$ iff $|N(S)|\ge |S|$ for every $S\subseteq A$. Starting with a maximum matching, an unmatched vertex and its alternating reachable set would violate Hall unless an augmenting path exists; flipping along that path increases the matching, proving sufficiency.

Every vertex cover meets each edge of a matching, so $\gamma \le \beta$. Endpoints of a maximal matching cover every edge, so $\beta \le 2\gamma$. A disjoint union of $k$ triangles has $(\gamma ,\beta )=(k,2k)$. For $T_3(30)$, $\gamma =15$ and $\beta =30-10=20$. In bipartite graphs the alternating-path proof constructs a cover of size equal to a maximum matching, giving König theorem.

The chromatic index is the minimum number of matchings partitioning the edges. Label vertices of $K_{2^r}$ by the vector space over ${\mathbb{F}}_2$; for each nonzero $a$, pair $x$ with $x+a$. These $2^r-1$ perfect matchings partition all edges, while degree gives the matching lower bound, so $\chi \prime =n-1$.

Solved by gpt-5.6-sol high.