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

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.

Solved by gpt-5.6-sol high.