Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2006/iii/paper-37/1/b/solution
Past exam of the mathematics course of the University of Cambridge 2006 iii Paper 37 1 b Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-14
Let be an edge of . Apply the preceding result with source and sink . A tree contains exactly when its unique path from to is the single edge , in the positive direction. Consequently the unit electrical current on is . 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 , where is the electrical unit current and has zero divergence. Since is a potential difference, summation by parts gives . Thus its energy is , minimized by . The energy of equals its terminal voltage drop, hence the effective resistance.
Extend any unit flow on to 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 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.
New to topics? Read the docs here!