= Solution
Fix an <edge> $e=\{u,v\}$ and orient it from $u$ to $v$. For each <spanning tree> $T$, let $\gamma_T$ be its unique <graph path> from $u$ to $v$. Assign a signed unit <graph path> flow $j_T$ to oriented <edges>: value $+1$ in the direction used by $\gamma_T$, value $-1$ on the reversed orientation, and zero otherwise. Define its mean
$$
J(x,y)=\mathbb E\,j_T(x,y).
$$
Each $j_T$ has net divergence one at $u$, minus one at $v$ and zero elsewhere, so $J$ is a <unit flow>. The <mean spanning-tree path current> also satisfies the <Kirchhoff cycle law>. Although its verification is permitted to be omitted, a short counting argument makes it explicit. Let $\mathcal F_{uv}$ be the <two-component spanning forests> separating $u$ and $v$, write $A_F$ for the component containing $u$, and let $N_T$ be the number of <spanning trees>. Deleting an <edge> used by the oriented <tree> <graph path> gives one such forest. Conversely adjoining an <edge> across its two components gives a unique <tree> with that <edge> on its $u$-to-$v$ <graph path>. Consequently
$$
J(x,y)=\frac1{N_T}\sum_{F\in\mathcal F_{uv}}\bigl(\mathbf1_{A_F}(x)-\mathbf1_{A_F}(y)\bigr)=h(x)-h(y),\qquad h(x)=\frac1{N_T}\sum_{F\in\mathcal F_{uv}}\mathbf1_{A_F}(x).
$$
The gradient form proves the <Kirchhoff cycle law> directly and is <Ohm's law> for unit <edge> resistance. The <Kirchhoff node law> then gives $Lh=\delta_u-\delta_v$, and the electrical <unit flow> is unique: the difference between two such <voltages> is a <harmonic function on a graph> and hence constant on the connected finite <graph>.
If $e\in T$, its single-edge route is the unique <tree> <graph path> from $u$ to $v$, so $j_T(u,v)=1$. If $e\notin T$, that <tree> <graph path> does not use $e$, so $j_T(u,v)=0$. Therefore
$$
J(u,v)=\mathbb P(e\in T).
$$
By <Ohm's law>, $J(u,v)=h(u)-h(v)$; for a unit terminal current, this <voltage> difference is exactly the <effective resistance> between the terminals. We have proved the requested <edge-inclusion formula for a uniform spanning tree>:
$$
\boxed{\mathbb P(e\in T)=R_{\mathrm{eff}}(u,v).}
$$
Now use <linearity of expectation> and the fact that every <spanning tree> has exactly $n-1$ <edges>. This gives <Foster's theorem>:
$$
\boxed{\sum_{e\in E}R_{\mathrm{eff}}(e)=\sum_{e\in E}\mathbb P(e\in T)=\mathbb E|T|=n-1.}
$$
The sums here use unoriented <edges> exactly once. For unit conductance this is the displayed identity; with conductances $c_e$ the inclusion <probability> and summand become $c_eR_{\mathrm{eff}}(e)$.
Back to article page
