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