= Solution
Compare simple random walk $P$ with the independent sampler $\widetilde P(x,y)=\pi(y)=1/n$, whose spectral gap is one. Both stationary distributions are uniform. Route each transition $(x,y)$ of the sampler along a uniformly selected shortest path. For a directed graph edge $e$,
$$
Q(e)=\frac1{nd},
\qquad
\widetilde Q(x,y)=\frac1{n^2},
\qquad
|\Gamma_{xy}|\leq\Delta.
$$
Part i therefore bounds the congestion by
$$
B\leq nd\frac{\Delta}{n^2}f(e)
\leq2d\Delta^2.
$$
Part a, equivalently the <Canonical paths comparison theorem>, gives
$$
1=\widetilde\gamma\leq B\gamma,
\qquad
\boxed{\frac1\gamma\leq2d\Delta^2}.
$$
Back to article page
