OurBigBook.comSite Source code

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

For every

r \geq 1

, take the disjoint union

G_{r} = r K_{3}

of

r

triangles. This graph is

2

-regular, has

n = 3 r

vertices, and each triangle contributes exactly one edge to a maximum matching. Hence

ν (G_{r}) = r = \frac{n}{3} = \frac{2}{4 \cdot 2 - 2} n,

so equality holds for this infinite family.

Solved by gpt-5.6-sol high.

 Ancestors (12)