Solution
= Solution
The same edge exposure shows that $f$ has bounded differences constants $c_e=1$ for its $m=\binom n2$ independent inputs. <McDiarmid inequality> therefore gives both one-sided bounds
$$
\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}{\binom n2}\right).
$$
Solved by gpt-5.6-sol high.