How to efficiently sample edges from a graph in relation to its spanning tree Consider a connected, unweighted, undirected graph $G$. Let $m$ be the number of edges and $n$ be the number of nodes.
Now consider the following random process. First sample a uniformly random spanning tree of $G$ and then pick an edge from this spanning tree uniformly at random. Our process returns the edge.
If I want to sample many edges from  $G$ from the probability distribution implied by this process, is there a more efficient  (in terms of computational complexity) method than sampling a new random spanning tree each time?

Approximately sampling according to the effective resistances is done in the sparsification algorithm of Spielman and Srivastava. See Theorem 2 of this paper. The complexity has a one-off cost of $\tilde{O}(m)$, and then cost $\tilde{O}(1)$ per sample.
