Group the edge indicators into $n-1$ independent blocks
$$
B_i=(X_{ij}:j>i),
\qquad1\leq i<n.
$$
All edges in one block share vertex $i$. Replacing the entire block can change the maximum matching number by at most one: after deleting the at most one matched edge incident to $i$, a matching from either graph remains valid in the other. Applying <McDiarmid inequality> to these $n-1$ blocks gives
$$
\mathbb P(f(G)-\mathbb Ef(G)\geq t),
\quad
\mathbb P(f(G)-\mathbb Ef(G)\leq-t)
\leq\exp\!\left(-\frac{2t^2}{n-1}\right).
$$

Solved by gpt-5.6-sol high.

Solution

Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 208 / 4 / c / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2026/iii/paper-208/4/c/solution