= Solution
Let $d=d_G(a,b)>0$, and for $i=1,\ldots,d$ put
$$
U_i=\{x:d_G(a,x)<i\},\qquad \Pi_i=\partial_eU_i.
$$
Each <edge cutset> $\Pi_i$ separates $a$ from $b$. Adjacent vertices have <graph distances> from $a$ differing by at most one. Hence an edge can cross at most one of these level boundaries, so the <edge cutsets> are pairwise edge-disjoint. Write $k_i=|\Pi_i|\geq1$; then $\sum_i k_i\leq|E|$.
The <Nash-Williams inequality> for unit conductances gives
$$
R_{\mathrm{eff}}(a,b)\geq\sum_{i=1}^d\frac1{k_i}\geq\frac{d^2}{\sum_i k_i}\geq\frac{d^2}{|E|},
$$
where the middle inequality is the <Cauchy-Schwarz inequality>. One can also derive the first inequality directly: every <unit flow> has signed net flux one through each $\Pi_i$, so its <energy of a flow> on that cut is at least $1/k_i$; sum over the disjoint cuts and use the <Thomson principle>.
Combining with the <commute time identity> yields
$$
\boxed{\mathbb E_a\tau_b+\mathbb E_b\tau_a=2|E|R_{\mathrm{eff}}(a,b)\geq2d_G(a,b)^2.}
$$
The case $a=b$ is trivial. A <path graph>, with $a,b$ its endpoints, attains equality.
Back to article page
