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

Orient the unique path from $s$ to $t$ in a uniform spanning tree $T$, and put $j_{xy}^T=1$ when it uses the edge from $x$ to $y$, $-1$ when it uses the reverse direction, and zero otherwise. Then the proposed current is $i_{xy}=\mathbb{E}{j}_{xy}^T$; set it to zero on nonedges. It is antisymmetric.

For each tree path, every intermediate graph vertex has one incoming and one outgoing path edge, while the source has one outgoing edge and the sink one incoming edge. HenceTaking expectations givesthe Kirchhoff node law for a unit flow.

To establish the Kirchhoff cycle law, it is not enough to check it separately for each tree path: those path currents need not satisfy the voltage law on the original graph. Instead, let $\mathcal{T}$ be all spanning trees and let ${\mathcal{F}}_{st}$ be all spanning forests with two components, one containing $s$ and the other $t$. For $F\in {\mathcal{F}}_{st}$ denote the source component by $C_s(F)$.

For an existing edge $xy$, deleting it from a tree whose $s$-$t$ path uses $x\to y$ produces precisely a forest $F\in {\mathcal{F}}_{st}$ with $x\in C_s(F)$ and $y\notin C_s(F)$. Conversely, adding $xy$ to any such forest produces exactly that tree and path orientation. This is a bijection. Applying it to both orientations givesDefine $h(x)=|\mathcal{T}{|}^{-1}{\sum }_F{1}_{x\in C_s(F)}$. Then $i_{xy}=h(x)-h(y)$ on every edge. Since the resistances are one, this is Ohm's law, and the voltage drops telescope around every oriented cycle:Together with the node law, this proves that the mean tree-path current is the electrical unit current. This argument is the mean spanning-tree path current identity.

For clarity, these laws determine the current uniquely. The difference of two solutions is a potential gradient $k(x)-k(y)$ with zero divergence. Multiplying its divergence by $k(x)$ and summing over graph vertices gives ${\sum }_{\{x,y\}}(k(x)-k(y){)}^2=0$. Thus every difference current is zero.

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.