Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 215 / 5

Thomson principle states that the effective resistance is the minimum energy of a unit flow from $a$ to $z$:An edge cutset separating $a$ and $z$ is a set of edges whose removal disconnects them. Every unit flow has net flux one across each such cutset ${\Pi }_k$. By Cauchy-Schwarz inequality,For disjoint cutsets, summing these energy lower bounds and applying Thomson's principle gives the Nash-Williams inequalityThe commute time identity is

There are $\asymp n^3$ edges. The $n^2$ horizontal cutsets between successive rows perpendicular to the long direction are disjoint and each contains $\asymp n$ unit-conductance edges. Nash-Williams inequality givesConversely, spread a unit flow nearly uniformly across the width $n$ while moving it through the $n^2$ long-direction layers, with bounded extra energy to fan out from and collect at the two corner vertices. Its energy is $O(n^2/n)+O(\log n)=O(n)$, so Thomson's principle gives the matching upper bound $R_{\mathrm{eff}}\asymp n$.

The graph is invariant under a half-turn exchanging the two corners, so the two directional hitting-time expectations are equal. The commute time identity therefore yields