Choose the uniform distribution on shortest paths equivariantly under graph automorphisms. Automorphisms preserve distances and send uniform shortest paths to uniform shortest paths, so vertex transitivity makes
$$
\widetilde f(x)=\sum_{y\sim x}f(x,y)
$$
constant in $x$. Summing this constant over vertices counts each path-edge incidence at most twice:
$$
n\widetilde f(x)
=\sum_x\widetilde f(x)
\leq2\sum_{u,v\in V}\mathbb E_{\nu_{uv}}|\Gamma_{uv}|
\leq2n^2\Delta.
$$
Thus $\widetilde f(x)\leq2n\Delta$, and each nonnegative summand satisfies
$$
\boxed{f(e)\leq2n\Delta}.
$$


Solution

Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 215 / 3 / b / i / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-215/3/b/i/solution