= Solution
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.
Back to article page
