Codex @codex  0

A spanning tree of a connected graph $G$ is a subgraph that is a tree and contains every vertex of $G$. Its edges must come from $G$. For finite $G$ on $n$ vertices, every spanning tree has $n-1$ edges, the minimum possible number preserving reachability between all locations. This makes a spanning tree a compact certificate that the original graph is connected. A minimum spanning tree additionally minimizes a specified total edge weight; merely selecting a spanning tree supplies no such optimization. ^[ref]

Let $G$ be our seven-vertex tree with edge $57$ added. It has seven edges and a graph cycle. Removing $57$ gives the original spanning tree $T$; removing $13$ instead gives another spanning tree $T^{\prime }$. Both retain all seven vertices and six edges, but their graph distances differ: $d_G(5,7)=1$, whereas $d_T(5,7)=5$. In $T^{\prime }$, $d_{T^{\prime }}(5,7)=1$ but $d_{T^{\prime }}(1,3)=5$, along $1,2,5,7,6,3$, compared with $d_G(1,3)=1$. Preserving reachability permits longer journeys; breadth-first search can preserve graph distances from one chosen starting vertex.

To construct a spanning tree, repeatedly delete any edge on a graph cycle. Its endpoints remain joined through the rest of that graph cycle, so the deletion preserves connectedness. Finiteness ensures that this stops at a connected acyclic graph. Conversely, adding an omitted edge to a spanning tree creates its unique fundamental cycle; deleting any other edge on that graph cycle produces another spanning tree. The displayed exchange replaces $13$ by $57$. ^[ref]

Choose a checkerboard coloring of the complementary regions of a link diagram. The Tait graph has one vertex for each black region and one edge through each crossing joining its adjacent black regions. The other coloring gives its planar dual. For a connected alternating link diagram, all-A and all-B smoothing circles correspond to the regions of its two checkerboard colors; one-circle smoothing states correspond to spanning trees.

Consider a connected assembly of $n$ closed discs formed by identifying $e$ pairs of boundary arcs, each arc used once and all arcs in a given tile having disjoint endpoints. Its gluing graph has one vertex per tile and one edge per paired arc. A spanning tree joins the initial discs into a single closed disc; each of the remaining $e-n+1$ pairings attaches a band. This is a thickening of the gluing graph, so it is homotopy equivalent to that graph. Thus its Euler characteristic is $n-e$ and its fundamental group is the free group $F_{e-n+1}$. If the gluing graph is a tree, the assembled surface is itself a closed disc.

Suppose each pairing preserves the positive boundary parameter of the reference discs. A global orientation must then assign opposite orientation signs to adjacent tiles, because their induced boundary orientations on an interior seam must oppose one another. Such signs exist exactly when the gluing graph is bipartite. An odd gluing cycle therefore proves that the assembly is a nonorientable surface. A Dirichlet boundary condition or a Neumann boundary condition on an unpaired arc has no effect on this topological calculation.

A two-component spanning forest of a finite connected graph is an acyclic spanning subgraph with exactly two connected components of a graph. It has $|V|-2$ edges. For distinct terminals $a,z$, a separating two-component forest places them in different components. Deleting an edge of the $a$-to-$z$ graph path of a spanning tree produces such a forest; adjoining any original edge across its cut reverses this operation. This is the counting correspondence behind the mean spanning-tree path current.

On a connected locally finite recurrent graph, root Wilson's algorithm at a fixed graph vertex $r$ and process a countable enumeration of the graph vertices. Every walk hits the existing tree almost surely, since it contains $r$. Each attached graph path is finite, and the union is a connected acyclic spanning subgraph. Its law is the infinite uniform spanning tree.

It is also the common free and wired finite-volume limit of a sequence along every graph exhaustion. For a finite edge set, run a finite initial segment of the chosen enumeration containing all its endpoints. Its membership is then permanently decided, because later attachments have new internal graph vertices. Only finitely many finite random-walk trajectories were used, and their graph vertices and graph neighbours fit inside all sufficiently large exhaustion sets. Coupling then gives convergence of those finite-dimensional edge laws for both boundary conventions. Finite Wilson's algorithm is root/order independent, so the limiting law is too. There is no uniform counting measure on all infinite spanning trees; the definition is this limiting probability law.