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

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.