= Solution
Choose a <spanning tree> $T$ of $G$, rooted at $a$. A <depth-first traversal of a tree> gives a deterministic closed walk
$$
v_0=a,v_1,\ldots,v_{2(n-1)}=a
$$
that traverses each edge of $T$ once in each direction and visits every vertex. Define <stopping times> $S_0=0$ and
$$
S_{j+1}=\inf\{t\geq S_j:X_t=v_{j+1}\}.
$$
The <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>,
$$
\mathbb E_a S_{2(n-1)}=\sum_{j=0}^{2(n-1)-1}\mathbb E_{v_j}\tau_{v_{j+1}}.
$$
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> gives
$$
\mathbb E_a\tau_{\mathrm{cov}}\leq\sum_{\{u,v\}\in T}\bigl(\mathbb E_u\tau_v+\mathbb E_v\tau_u\bigr)=2|E|\sum_{\{u,v\}\in T}R_{\mathrm{eff}}^G(u,v).
$$
The <effective resistances> are measured in the original <graph>, where each tree-edge pair is adjacent. Part (a) therefore bounds every summand by one, so
$$
\boxed{\mathbb E_a\tau_{\mathrm{cov}}\leq2(n-1)|E|.}
$$
For the one-vertex <graph>, the <cover time> is zero and the same bound is immediate.
Back to article page
