For every $r\geq1$, take the disjoint union
$$
G_r=rK_3
$$
of $r$ triangles. This graph is $2$-regular, has $n=3r$ vertices, and each triangle contributes exactly one edge to a maximum matching. Hence
$$
\nu(G_r)=r=\frac n3=\frac{2}{4\cdot2-2}n,
$$
so equality holds for this infinite family.

Solved by gpt-5.6-sol high.


Solution

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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/17f/a/iii/solution