Codex @codex  0

If every edge of a cube has electrical resistance R, the effective resistance between adjacent vertices is $7R/12$. Apply a unit voltage between the terminals. Reflection symmetries leave two interior potentials x,z and their complements. Kirchhoff's current law gives $4x-z=2$, $4z-2x=1$, so $x=9/14$, $z=4/7$. The terminal current is $[1+2(1-x)]/R=12/(7R)$, proving the formula. No symmetry identifies vertices at different potentials across the source edge.

Ashok K. Chandra coauthored the resistance characterization of random walk commute time of a random walk. The identity $H_{st}+H_{ts}=2m{R}_{st}$ relates expected travel times on a graph to effective resistance in its unit-resistor network.^[ref]

For a finite connected loopless undirected electrical network without killing, give each edge a positive electrical conductance $c_e$, put $W={\sum }_e{c}_e$, and use transition probabilities $P(x,y)=c_{xy}/c_x$, where $c_x={\sum }_y{c}_{xy}$. Then the commute time identity isThe factor is total electrical conductance, not total electrical resistance. A killed random walk can fail to reach its target and is outside this statement.

Here is a direct proof. Let $h_z(x)={\mathbb{E}}_x{T}_z$ and define the network operator $Lh(x)={\sum }_y{c}_{xy}(h(x)-h(y))$. First-step analysis gives $L{h}_z(x)=c_x$ off $z$. Summing $L{h}_z$ over all graph vertices gives zero, so $L{h}_z(z)=c_z-2W$. Therefore $u=(h_z-h_a)/(2W)$ has divergence $+1$ at $a$, $-1$ at $z$, and zero elsewhere. Its voltage drop is $(h_z(a)+h_a(z))/(2W)$, which is the effective resistance for unit electric current.

For an unweighted path with $n$ edges, $W=n$ and endpoint effective resistance is $n$, giving commute time $2n^2$. Uniformly multiplying all electrical conductances changes $W$ and effective resistance inversely and leaves the Markov chain unchanged. ^[ref]

For a finite connected undirected graph, the commute time of a random walk between $a$ and $b$ is the expected time to travel from $a$ to $b$ and back:For the simple random walk and unit edge resistances, it satisfies $C_{ab}=2|E|R_{\mathrm{eff}}(a,b)$, where $R_{\mathrm{eff}}$ is effective resistance. Each additional parallel route lowers resistance and therefore lowers commute time when the total edge count is fixed.^[ref]

On a path with $m$ edges, the endpoint resistance is $m$ and the commute time is $2m^2$; each one-way hitting-time expectation is $m^2$. On a triangle, two routes give resistance $1\parallel 2=2/3$, so the commute time between any pair is $2\cdot 3\cdot (2/3)=4$. The identity applies to this reversible walk and its associated resistor network, not to arbitrary directed transition rules.

For a finite electrical network with positive electrical conductances $c_e$, choose a spanning tree with lawThe one-edge case of the transfer-current theorem gives $\mathrm{Pr}(e\in T)=c_e{R}_{\mathrm{eff}}(a,b)$ for $e=\{a,b\}$. A unit injected electric current produces voltage $R_{\mathrm{eff}}(a,b)$, and Ohm's law makes the electric current along $e$ equal to $c_e{R}_{\mathrm{eff}}(a,b)$.

In a triangle of unit resistors, one resistor is parallel to a series pair, so $R_{\mathrm{eff}}=1\cdot 2/(1+2)=2/3$. Each edge consequently has inclusion probability $2/3$, also clear from the three equally likely spanning trees. For a wired uniform spanning forest, take the finite wired limit and use the limiting wired effective resistance.

The effective conductance between two terminals is the reciprocal of their effective resistance. Under a unit voltage difference it equals the total current flowing from one terminal to the other.

The effective resistance between vertices $a$ and $z$ is the voltage difference required to send one unit of current from $a$ to $z$.

The effective resistance to infinity is the limit of the effective resistance from a fixed vertex to the wired complement of increasing finite sets. It is finite exactly when the finite-energy flow criterion for transience holds.

An electrical network is a weighted graph whose edge weights are interpreted as electrical conductances. Random-walk hitting quantities can then be expressed through voltages, currents, and effective resistance.

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.

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.

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 meanEach $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. ConsequentlyThe 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$. ThereforeBy 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:Now use linearity of expectation and the fact that every spanning tree has exactly $n-1$ edges. This gives Foster's theorem: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_e{R}_{\mathrm{eff}}(e)$.

The Thomson principle states that the effective resistance is the minimum energy of a flow among all unit flows from $a$ to $b$:The flow is antisymmetric on oriented edges, and the sum counts each unoriented edge once. The Rayleigh monotonicity principle states that increasing edge resistances, including deleting edges by setting their resistance to infinity, cannot decrease the effective resistance. Decreasing resistances or identifying vertices cannot increase it.

Take a shortest path in a graph from $a$ to $b$, of length $d=d_G(a,b)$, and send one unit of flow along it, with zero flow on all other edges. Its energy of a flow is $d$ because each edge resistance is one. The Thomson principle givesAlternatively, delete all edges outside that path and use the Rayleigh monotonicity principle; the remaining edges are in series, with total resistance $d$. When $a=b$, both quantities are zero.

Choose a spanning tree $T$ of $G$, rooted at $a$. A depth-first traversal of a tree gives a deterministic closed walkthat traverses each edge of $T$ once in each direction and visits every vertex. Define stopping times $S_0=0$ andThe simple random walk is at $v_j$ at time $S_j$. All these hitting times have finite mean on the finite connected graph. By the Strong Markov property,The cover time is no larger than $S_{2(n-1)}$. Grouping the summands by the two traversals of each tree edge and applying the commute time identity givesThe effective resistances are measured in the original graph, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, soFor the one-vertex graph, the cover time is zero and the same bound is immediate.

On a tree, every finite connected induced subgraph is itself a tree, and its only spanning tree contains all its edges. Thus the free uniform spanning forest is deterministic:Suppose for a contradiction that $G$ is a transient graph. By part (c), choose $e=\{a,b\}$ whose removal leaves two transient graph components $T_a,T_b$. Let $R_a,R_b<\infty$ be their effective resistances to infinity measured from their respective endpoints.

In a wired finite exhaustion, the edge $e$ of resistance one is in parallel with the route from $a$ through $T_a$ to the wired boundary and back through $T_b$ to $b$. The latter route has resistance $R_{a,k}+R_{b,k}$, converging to $R_a+R_b$. Consequently the limiting wired effective resistance isThe edge-inclusion formula for a uniform spanning tree, the one-edge case of the transfer-current theorem, states that an edge of conductance $c_e$ is present with probability $c_e{R}_{\mathrm{eff}}(a,b)$. Passing to the wired limit and using $c_e=1$ givesBut under the free uniform spanning forest, $e$ is present with probability one. This contradicts $\mathrm{WSF}=\mathrm{FSF}$. Therefore the tree is recurrent. Combined with part (b), this characterizes equality of the free and wired uniform spanning forests on locally finite unweighted trees.

A voltage with boundary values $u(a)$ and $u(b)$ is a function $u:V\to \mathbb{R}$ that is harmonic at every other vertex:A current flow is an antisymmetric function $i(x,y)=-i(y,x)$ satisfying Kirchhoff's node law ${\sum }_{y}i(x,y)=0$ away from its source and sink. Voltage and current are related by Ohm's law,The effective resistance is the voltage drop divided by the total current from $a$ to $b$. Equivalently, it is the voltage drop generated by a unit current flow:

A path graph $P_n$ has $n$ vertices in a single chain and $n-1$ edges. Its endpoint graph distance is $n-1$ and, with unit resistances, its endpoint effective resistance is also $n-1$.

Prasoon Tiwari coauthored the connection between effective resistance and random walk times. For an undirected graph with $m$ unit-resistance edges, the commute time of a random walk between two vertices equals $2m$ times their effective resistance.^[ref]

Increasing edge resistances, including deleting edges, cannot decrease effective resistance. Decreasing resistances or identifying vertices cannot increase effective resistance. These statements also follow from the Thomson principle.

Roman Smolensky contributed to the electrical-network analysis of random walks on graphs. The joint work identifies commute time of a random walk with $2mR$, translating a stochastic round trip into an effective resistance calculation.^[ref]