= Solution
For finite $G$, choose a root $r$ and an ordering of the other <graph vertices>. Begin with a <tree> consisting only of $r$. At each stage take the first <graph vertex> not already in the <tree>, run an independent <simple random walk> from it until its first hit of the existing <tree>, erase the loops chronologically, and add the resulting <graph path>. In chronological <loop erasure>, revisiting a <graph vertex> already in the current list deletes all list entries after that <graph vertex>; otherwise append the new <graph vertex>. The retained final <graph path> is simple, with new internal <graph vertices> and exactly one endpoint in the old <tree>. Adding it therefore preserves connectedness and creates no <graph cycle>. <Graph vertices> already included are skipped. On a finite <connected graph> each walk hits the existing <tree> <almost surely>; after finitely many attachments all <graph vertices> are present.
The <Wilson algorithm> theorem states that this <tree> is a <uniform spanning tree>, independently of the chosen root and order. The required hypotheses here are an undirected connected finite <graph> and transition <probabilities> proportional to conductance; unit conductances give <simple random walk> and the uniform law. This is the sampling result being described, not a claim that arbitrary walk transition <probabilities> would produce a uniform <tree>.
For an infinite connected locally finite <recurrent graph>, choose a fixed finite root $r$ and enumerate all <graph vertices>. A connected <locally finite graph> is countable, since its finite-radius balls are finite. Run the same algorithm successively. Recurrence and irreducibility imply that a walk from any <graph vertex> hits $r$ <almost surely>, hence hits the current <tree>. Every attached <graph path> is therefore finite. The countable intersection of these probability-one events has <probability> one, and the increasing union is an acyclic connected subgraph containing all <graph vertices>: each <graph vertex> receives a finite route to $r$.
This gives the <uniform spanning tree of a recurrent infinite graph>. It is not a uniform counting measure on all infinite <spanning trees>. Equivalently, its joint <probability distributions> on finite collections of <edges> are the common limits of <uniform spanning trees> along any <graph exhaustion>, using the approximations defining the <free uniform spanning forest> and the <wired uniform spanning forest>. To check that equivalence, fix a finite <edge> set $F$ and run the chosen enumeration through a finite prefix containing all its endpoints. Once those <graph vertices> are in the <tree>, later attachments cannot add an <edge> with both endpoints already included, so membership of $F$ is settled permanently. Only finitely many random walks have been used; each has a finite trajectory <almost surely>. All their visited <graph vertices> and all their <graph neighbours> lie in a sufficiently large exhaustion set. Couple finite-volume and infinite-volume walks with the same steps there. Whether the exterior is deleted or wired to one boundary <graph vertex>, these initial trajectories and their loop erasures then agree. This proves convergence of the <probabilities> of <cylinder sets> determined by those <edges>.
The limiting law is unchanged by the root and ordering because the laws on finite <graphs> have this invariance. The same coupling shows that changing the exhaustion also leaves the law unchanged. Thus
$$
\boxed{\text{recurrent }G:\quad\text{fixed-root Wilson tree}=\text{free limit}=\text{wired limit}.}
$$
The result is a single <spanning tree> because the <graph> is recurrent. On a <transient graph>, infinite-volume spanning-tree limits may instead be <uniform spanning forests>; recurrence cannot be omitted from this conclusion.
Back to article page
