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

Group the edge indicators into $n-1$ independent blocksAll 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