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