Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 37 / 1 / b / Solution

Let $e=\{a,b\}$ be an edge of $G$. Apply the preceding result with source $a$ and sink $b$. A tree contains $e$ exactly when its unique path from $a$ to $b$ is the single edge $e$, in the positive direction. Consequently the unit electrical current on $e$ is $\mathbb{P}(e\in T)$. By Ohm's law and the definition of effective resistance,since this edge has unit resistance. This is the unit-conductance case of the edge-inclusion formula for a uniform spanning tree.

The general principle needed is Rayleigh monotonicity principle: adding edges, or decreasing their resistances, cannot increase the effective resistance between fixed terminals. One precise variational formulation is the Thomson principle:with one orientation chosen for each unoriented edge. To see this, write any unit flow as $i+k$, where $i$ is the electrical unit current and $k$ has zero divergence. Since $r_e{i}_e$ is a potential difference, summation by parts gives ${\sum }_e{r}_e{i}_e{k}_e=0$. Thus its energy is ${\sum }_e{r}_e{i}_e^2+{\sum }_e{r}_e{k}_e^2$, minimized by $i$. The energy of $i$ equals its terminal voltage drop, hence the effective resistance.

Extend any unit flow on $G$ to $G^{\prime }$ by zero on all new edges. It is still a unit flow, including at new graph vertices, and its energy is unchanged. The variational minimum on $G^{\prime }$ is therefore no larger. Using the edge-inclusion formula in both graphs givesThe graphs are understood to be finite and connected, as required for their uniform spanning-tree laws. The comparison allows added graph vertices as well as added edges.