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

There are $m=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ independent edge indicators. Conditional on all indicators except one, changing that edge changes the maximum matching number by at most one. The conditional range is therefore at most one, so Popoviciu inequality on variances bounds each conditional variance by $1/4$. The tensorized conditional-variance inequality gives

Solved by gpt-5.6-sol high.