Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 214 / 3

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.

Let $d=d_G(a,b)>0$, and for $i=1,\dots ,d$ putEach edge cutset ${\Pi }_i$ separates $a$ from $b$. Adjacent vertices have graph distances from $a$ differing by at most one. Hence an edge can cross at most one of these level boundaries, so the edge cutsets are pairwise edge-disjoint. Write $k_i=|{\Pi }_i|\ge 1$; then ${\sum }_i{k}_i\le |E|$.

The Nash-Williams inequality for unit conductances giveswhere the middle inequality is the Cauchy-Schwarz inequality. One can also derive the first inequality directly: every unit flow has signed net flux one through each ${\Pi }_i$, so its energy of a flow on that cut is at least $1/k_i$; sum over the disjoint cuts and use the Thomson principle.

Combining with the commute time identity yieldsThe case $a=b$ is trivial. A path graph, with $a,b$ its endpoints, attains equality.