When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $P_n$ has cover time $C(P_n) = \Theta(n^2)$ while the ($\frac{n}{2}$, $\frac{n}{2}$)-lollipop graph $L_{\frac{n}{2}, \frac{n}{2}}$ has cover time $C(L_{\frac{n}{2}, \frac{n}{2}}) = \Theta(n^3)$. Eventually adding edges does decrease the cover time because the complete graph $K_n$ has cover time $C(K_n) = \Theta(n \log n)$ by analogy to the coupon collector problem.
Under what assumptions though would the supposed intuition hold true? Specifically, what about vertex transitivity?
Let $G$ be a vertex-transitive graph with $n$ vertices. Consider any vertex-transitive graph $G^+$ obtained from $G$ by adding edges (i.e. both $G$ and $G^+$ are vertex transitive and $G$ is a spanning subgraph of $G^+$).
Is it the case that $C(G^+) \le C(G)$?
