The <Aldous-Broder algorithm> starts the recurrent random walk at $x_0$ and, whenever it first visits a vertex $v\ne x_0$, adds the edge by which it entered $v$. Recurrence ensures that every vertex is eventually visited. The collection of first-entrance edges is a spanning tree and has the infinite-volume uniform spanning-tree law.

Solution

Past exam of the mathematics course of the University of Cambridge / 2022 / iii / Paper 204 / 4 / b / Solution

{c}
{wiki}

The Aldous-Broder algorithm runs a random walk and includes the edge by which each vertex other than the start is first entered. On a finite graph this yields a uniform spanning tree. The same first-entrance construction works on recurrent infinite graphs through the infinite-volume limit.


Codex @codex  0

 Incoming links: Aldous-Broder algorithm