Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 30 / 1

Orient each edge both ways. A unit flow $j$ from $x$ to $y$ is antisymmetric, $j(u,v)=-j(v,u)$, with divergence of a flow equal to $+1$ at $x$, $-1$ at $y$ and zero elsewhere. Its energy iswhere each unoriented edge is counted once. Put $c_e=1/r_e$. The electrical unit current is $i(u,v)=c_{uv}(V(u)-V(v))$, where the potential $V$ solves the Kirchhoff node law with those source and sink divergences. Because $G$ is a connected graph, this potential is unique up to an additive constant. The effective resistance is the electric potential difference needed for unit current,Discrete summation by parts gives ${\mathcal{E}}_r(i)={\sum }_{u}V(u)\mathrm{div}i(u)=R(x,y)$.

The Thomson principle says that this current minimizes energy among all unit flows. Indeed write any other unit flow as $j=i+k$, where $\mathrm{div}k=0$. ThenConsequentlyThis also proves uniqueness of the minimizing current.

If $r_e^{\prime }\ge r_e$ for every edge, then ${\mathcal{E}}_{r^{\prime }}(j)\ge {\mathcal{E}}_r(j)$ for every admissible flow. The admissible set is unchanged, so taking its minimum proves the Rayleigh monotonicity principle:Deletion is the limiting operation $r_e\to \infty$: finite-energy flows must then carry zero current on that edge. If the terminals become disconnected, the effective resistance is infinite.

Use $T_y=\inf \{n\ge 0:X_n=y\}$ and the positive return time $T_x^{+}=\inf \{n\ge 1:X_n=x\}$. The walk has transitions $p_{uv}=c_{uv}/d(u)$, $d(u)={\sum }_v{c}_{uv}$; its transition matrix defines a reversible Markov chain, although the transition probabilities need not be symmetric.

The voltage $h(u)=P_u(T_x<T_y)$ equals one at $x$, zero at $y$, and is a harmonic function on a graph away from the terminals: $h(u)={\sum }_v{p}_{uv}h(v)$. For this unit electric potential difference the electric current isThe first-step analysis therefore proves the return probability from effective resistance identity:Finite irreducibility ensures eventual hitting of one of the terminals, so no missing escape event appears in this finite-network calculation.

For an infinite locally finite connected graph, exhaust it by finite sets and wire their exteriors to one sink. The event of exiting before the first return decreases to the event of never returning. Thuswith $1/\infty =0$. In particular recurrence is equivalent to infinite effective resistance to infinity.

After deleting an edge, consider any infinite component and choose a root $o$ away from that edge's endpoints. Its vertex degree $d(o)$ is unchanged. On every finite wired exhaustion the Rayleigh monotonicity principle makes the resistance no smaller; the limit of a sequence does too. A recurrent original network consequently leaves a recurrent component. Finite components give recurrent walks as well, with an isolated graph vertex viewed as an absorbing state. This proves that edge deletion preserves recurrence. The phrase “no less recurrent” refers to this recurrence comparison: at a deleted-edge endpoint the vertex degree factor also changes, so monotonicity of its first-return probability alone should not be inferred.