Algorithm
1. Pick root. 2. Repeat: pick any unrooted vertex v. Do random walk from v until hitting tree. Loop-erase (remove cycles). Add to tree.
Advertisement
Loop erasure
When walk revisits vertex, delete cycle between visits. Keep only simple path.
Advertisement
Correctness
Non-trivial theorem: distribution is uniform over spanning trees. Independent of walk order.
Complexity
Expected O(V·h_G) where h_G = hitting time. For 'nice' graphs: O(V log V).