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

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 makesconstant in $x$. Summing this constant over vertices counts each path-edge incidence at most twice:Thus $\tilde{f}(x)\le 2n\Delta$, and each nonnegative summand satisfies