There are $m=\binom n2$ 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
$$
\operatorname{Var}(f(G))
\leq\sum_{e=1}^m\mathbb E\operatorname{Var}(f(G)\mid X_{-e})
\leq\frac m4=\frac1{4}\binom n2.
$$

Solved by gpt-5.6-sol high.

Solution

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

 Solution

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