Spanning tree

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]

Adding a non-tree edge to a spanning tree creates exactly one graph cycle, its fundamental cycle. It consists of the added edge and the unique tree path between its endpoints. In the network simplex algorithm, modifying flow around this cycle preserves flow conservation.

// Target: foundations-of-mathematics.bigb

A minimum spanning tree minimizes total edge weight among spanning trees of a connected weighted graph. It can be computed in polynomial time by repeatedly adding the least-weight edge joining two current components. The cut-exchange argument preserves the existence of an optimum containing every accepted edge. Removing an edge of a travelling-salesman tour gives a spanning tree, so its optimum is a lower bound on optimal tour cost.

Process edges in decreasing weight and delete an edge whenever the remaining graph stays connected. Previously retained heavier edges are bridges in a graph and remain so under deletion. Thus a deletable edge is heaviest on a current graph cycle, and the minimum spanning tree cycle property excludes it from every minimum spanning tree. At termination the surviving connected graph has no graph cycle, so it is a minimum spanning tree.

Process edges in increasing weight, accepting an edge exactly when its endpoints lie in different current connected components of a graph. A rejected edge can never cross a later component's boundary, since components only merge. Thus each accepted edge is lightest across the cut of a graph given by one current component. The minimum spanning tree cut property proves that the final spanning tree is minimum.

Start from one graph vertex. Repeatedly add the least-weight edge joining the reached graph vertices to an unreached graph vertex. Each step grows a tree and obeys the minimum spanning tree cut property. On a finite connected graph, the result is a minimum spanning tree.

The unique heaviest edge on a graph cycle belongs to no minimum spanning tree. If a spanning tree contains it, deleting it gives two components; the rest of the graph cycle has a lighter edge across that cut of a graph. Insert that edge to reduce the weight. This is the deletion certificate used by the reverse-delete algorithm.

The unique lightest edge across a cut of a graph belongs to every minimum spanning tree. If a spanning tree omits it, inserting it creates a graph cycle with another edge across that cut of a graph. Removing that heavier edge gives a lighter spanning tree, a contradiction. This proves the correctness of Prim algorithm and Kruskal algorithm for distinct weights.

A uniform spanning tree is sampled uniformly from all spanning trees of a finite connected graph.

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.

A uniform spanning forest is an infinite-volume limit of uniform spanning trees on finite graph approximations. Free and wired boundary identifications give the free uniform spanning forest and wired uniform spanning forest, respectively.

The free uniform spanning forest of an infinite locally finite graph is the weak limit of uniform spanning trees on finite induced connected exhaustions with free boundary. Every component is infinite almost surely.

For a uniform spanning tree, increasing events supported on disjoint sets of edges have nonpositive covariance. This negative association and the spatial Markov property imply monotonicity of free-boundary spanning-tree measures under exhaustion.

For oriented edges $e_1,\dots ,e_k$, the probability that their unoriented versions all belong to a uniform spanning tree is the determinant of the matrix of transfer currents between them. In particular, every finite forest that can be extended to a spanning tree has positive inclusion probability.

In a finite unweighted connected graph, take distinct graph vertices $a\ne z$ and orient the unique graph path from $a$ to $z$ in a uniform spanning tree and assign signed unit current to its edges. Its mean over trees is the electrical unit flow from $a$ to $z$. The Kirchhoff node law follows by averaging graph path divergences. For the graph cycle law, let ${\mathcal{F}}_{az}$ be the two-component spanning forests separating the terminals and $A_F$ the component containing $a$. Deleting a tree-path edge and conversely adjoining an edge across a forest cut are inverse operations. Hence the mean signed current on an edge $u\to v$ isThis is the gradient of $h(u)=|\mathcal{T}(G){|}^{-1}{\sum }_F{1}_{A_F}(u)$, proving the graph cycle law. In particular $R_{\mathrm{eff}}(a,z)=|{\mathcal{F}}_{az}|/|\mathcal{T}(G)|$. For an oriented existing edge $e=(a,z)$, that edge is used by the tree graph path exactly when it belongs to the tree, and then has positive orientation. Thus its mean current is $\mathbb{P}(e\in T)$, giving the edge-inclusion formula for a uniform spanning tree by Ohm's law.

For an edge $e=\{a,b\}$ of conductance $c_e$ in a finite electrical network, its inclusion probability in the conductance-weighted uniform spanning tree is $c_e{R}_{\mathrm{eff}}(a,b)$. The same formula holds for the wired limit using the limiting wired effective resistance.

On a transitive graph, the free and wired uniform spanning-forest measures are invariant and ergodic under the transitive automorphism group. Consequently every translation-invariant event has probability zero or one.

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.

Wilson's algorithm samples a uniform spanning tree by starting from a root and successively attaching loop-erased random walks from vertices not yet in the tree.

The wired uniform spanning forest of an infinite graph is the weak limit of uniform spanning trees on finite exhaustions whose exterior vertices are identified to one wired boundary vertex.

Wilson's algorithm rooted at infinity builds the wired uniform spanning forest on a transient graph by successively adding loop-erased random walks, run forever when they never hit the forest already constructed.

The number of trees in a wired uniform spanning forest is almost surely constant. This follows from its tail triviality together with the fact that every component is infinite.

A directed spanning tree rooted towards a vertex $r$ is a spanning tree whose edges are oriented so that every other vertex has a unique directed path to $r$.

The matrix-tree theorem expresses the weighted number of spanning trees of a finite graph as a cofactor of its Graph Laplacian. For a directed graph with out-Laplacian $L$, deleting the row and column indexed by a root $r$ giveswhere the sum runs over directed spanning trees rooted towards $r$.