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]

A spanning tree with greatest total edge weight. Apply Kruskal's algorithm in decreasing weight order, or negate every edge weight and compute a minimum spanning tree. Every graph path within a maximum spanning tree solves the widest path problem between its endpoints.

Suppose two spanning trees have the same first $n$ edges in nondecreasing weight order. If the first tree's next edge $e$ is no heavier than the second tree's next edge, it can be inserted into the second tree while preserving the common prefix and without increasing any sorted edge weight. If $e$ already occurs there, it ties for the next position. Otherwise its fundamental cycle contains an edge $f$ outside the prefix, since the prefix together with $e$ is acyclic. Every such $f$ is at least as heavy as $e$. Exchanging $f$ for $e$ preserves the spanning tree. Replacing a multiset entry by a no-larger entry cannot increase any order statistic. Tied edges can be ordered to preserve the prescribed prefix.

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 of a finite connected undirected weighted graph minimizes the sum of edge weights over all spanning trees. Kruskal's algorithm repeatedly accepts a least-weight edge joining different current connected components. The cut-exchange argument preserves an optimum containing every accepted edge, including when weights tie.

For nonnegative edge costs, an MST gives a lower bound on a travelling salesman tour: removing one tour edge leaves a spanning path whose cost is no greater than the tour cost, and the minimum spanning tree costs no more than that path.

Nonnegativity is needed for this comparison. A triangle with all three edge weights equal to minus one has tour cost $-3$ and minimum spanning tree cost $-2$, so the latter is not a lower bound. The MST optimization problem itself permits negative edge weights.

Let an edge set $F$ be contained in some minimum spanning tree, and let a cut of a graph have no crossing edge in $F$. Any least-weight edge crossing that cut of a graph can be added to $F$ while preserving its containment in some minimum spanning tree. Insert the chosen edge into an optimum containing $F$, then remove another crossing edge from the resulting graph cycle; it is no lighter and cannot belong to $F$. Ties imply existence of an optimum containing the chosen edge, rather than membership in every optimum.

Start with isolated vertices. In each round, determine the current connected components of a graph, choose a least-weight outgoing edge for each component, add their union, and recompute the components. With distinct weights, each chosen edge is the unique lightest edge across that component's graph cut. The minimum spanning tree cut property puts every such edge in every minimum spanning tree, so the selected edges remain acyclic. Every nonfinal component has an outgoing edge in a connected input, and merging makes progress until a spanning tree remains. Duplicate choices of the same edge are one set insertion.

Each new component contains at least two old components, so there are $O(\log |V|)$ rounds. Scanning all edges per round gives $O(|E|\log |V|)$ time. Equal edge weights require a consistent secondary order to avoid choosing a cycle of tied edges.

Otakar Borůvka formulated the distinct-cost minimum-connection problem in 1926.^[ref]

Sort the edge weights of a minimum spanning tree $T$ and of any spanning tree $S$ in nondecreasing order. Then $w_i(T)\le w_i(S)$ for every position. To prove it, fix a threshold $t$ and retain the graph's edges of weight at most $t$. If this graph has $c$ connected components, $T$ contains a spanning forest of each component using those edges: otherwise a light edge joining two of its pieces could replace an edge heavier than $t$ on its tree path, decreasing total weight. Hence exactly $|V|-c$ edges of $T$ have weight at most $t$. No other spanning tree can have more, since its retained edges form a forest inside those components. These threshold counts imply the coordinatewise inequality for sorted weights.

For a finite connected weighted graph with distinct edge weights, Kruskal's algorithm produces the unique minimum spanning tree. If another optimal tree existed, take an edge belonging only to the algorithm's tree and slightly increase its weight without changing the strict edge order. The algorithm then returns exactly the same tree, which must still be optimal, but the other tree's weight is unchanged and is now strictly smaller, a contradiction. Distinct weights are sufficient, not necessary: a triangle with weights $1,1,2$ has a unique optimum formed from the two weight-one edges.

Every path in a minimum spanning tree solves the bottleneck shortest path problem between its endpoints. If $e$ is a maximum-weight edge on the tree path, deleting it gives a graph cut separating the endpoints. A competing path with every edge lighter than $e$ would contain a crossing edge $f$; replacing $e$ with $f$ would decrease the tree's total weight, a contradiction. Equal weights cause no problem: the argument excludes a strictly smaller bottleneck and does not require a unique tree.

The reverse-delete algorithm processes edges of a finite connected undirected weighted graph in nonincreasing weight order, deleting an edge whenever the graph stays connected.

Maintain the invariant that the surviving graph contains some minimum spanning tree. A deletable edge $e$ lies on a cycle. Previously retained heavier edges are bridges and remain bridges after further deletions, so every other edge on that cycle has weight at most $w(e)$. If a current optimum contains $e$, removing it creates a cut. Another cycle edge $f$ crosses that cut; replacing $e$ by $f$ gives a surviving tree of no greater weight. Thus an optimum remains after deleting $e$.

At termination the graph is connected and acyclic, hence is itself a minimum spanning tree. With tied weights, $e$ need not be excluded from every optimum. On a triangle with all weights one, every edge belongs to some optimum, yet deleting any one edge is safe. The minimum spanning tree cycle property excludes an edge from every optimum only when it is uniquely heaviest on a cycle.

Kruskal's algorithm constructs a minimum spanning tree of a finite connected graph with undirected edges and real edge weights. Start with all vertices and no edges, a forest of isolated vertices. Sort the edges by nondecreasing weight, then accept an edge exactly when its endpoints belong to different current connected components of a graph. Otherwise reject it: the existing graph path between its endpoints would close a graph cycle. Each acceptance merges two connected components of a graph. Stop after $|V|-1$ acceptances, when the forest has become one spanning tree.

This is a greedy algorithm for economical network connection: only the next affordable connection and the current connected components of a graph matter. Unlike Prim's algorithm, which grows one reached tree, Kruskal's algorithm can grow several separate trees before joining them. The essential safeguard is avoiding a graph cycle, rather than simply buying the cheapest fixed number of edges.

Joseph Bernard Kruskal described this rule as Construction A on page 49 of his February 1956 paper, On the shortest spanning subtree of a graph and the traveling salesman problem; page 50 gives an exchange argument for distinct weights.^[ref]

Consider this original connected graph on vertices $A,B,C,D,E$. Its undirected edges, already in increasing weight order, areHere $AB$ means the unordered pair $\{A,B\}$; the weights are dimensionless costs. Accept $AB$ and $BC$, with total $3$. Reject $AC$: its endpoints already have the graph path $A,B,C$, so it would close the graph cycle $A,B,C,A$. Accept $CD$ and $DE$, reaching all five vertices with four edges. The resulting minimum spanning tree isStop here: $CE$ and $BE$ need not be examined. If processing continued, both would be rejected because their endpoints are already in the same connected component of a graph.

Taking the three cheapest edges $AB,BC,AC$ instead gives a graph cycle on $A,B,C$, leaving $D,E$ isolated: it is neither a forest nor a spanning tree. Even taking the four cheapest edges adds only $CD$ and leaves $E$ isolated. A cheap infeasible selection cannot compete with a minimum spanning tree. For this small graph, checking all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-edge subsets gives a direct certificate: among those that are spanning trees, exactly one has minimum cost $12$, namely $T$. The general algorithm avoids this exhaustive search.

An edge is safe for the current accepted forest $F$ if some minimum spanning tree contains both $F$ and that edge. The loop invariant is that some minimum spanning tree contains every accepted edge. It holds initially for the empty edge set. Suppose the next accepted edge $e$ joins a current connected component of a graph $S$ to its complement. No earlier rejected edge crosses this cut of a graph: once its endpoints are in one connected component of a graph, subsequent merges never separate them. Thus $e$ is a lightest edge across that cut of a graph.

For the short exchange argument, take a minimum spanning tree $T$ containing $F$. If $e$ is absent, adding it creates a fundamental cycle. This graph cycle contains another edge $f$ crossing the same cut of a graph. No edge of $F$ crosses the cut of a graph, so $f$ is not in $F$. Replace $f$ by $e$: the result is a spanning tree containing $F$ and $e$, with no greater total weight because $w(e)\le w(f)$. It is therefore also a minimum spanning tree. This is the minimum spanning tree cut property in the form needed for tied weights.

In the example, $CD$ is safe after rejecting $AC$: the current connected component of a graph $\{A,B,C\}$ has crossing edges $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest edge of the graph cycle $A,B,C,A$, so the minimum spanning tree cycle property excludes it from every optimum.

Negative and zero edge weights are allowed: the comparisons and exchange argument still apply. Ties can give several minimum spanning trees, though they need not; any order among equal-weight edges remains valid. Distinct edge weights guarantee a unique minimum spanning tree. To see why, take the lightest edge $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a cut of a graph; the other optimum has a graph path across it, containing an edge $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all edges to obtain a minimum spanning forest, one minimum spanning tree per original connected component of a graph; no spanning tree of the whole graph exists.^[ref]

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]

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.

In a finite connected graph with unit electrical resistance on each edge, choose distinct undirected edges $e_1,\dots ,e_k$ and orient each once. Define the transfer current $K(e,f)$ as the signed electric current through $f$ when one unit of electric current enters the tail of $e$ and leaves its head. For a uniform spanning tree $T$,Reversing one orientation negates its row and column, leaving the determinant unchanged. Distinctness is necessary: repeating an edge repeats a row and gives zero, although its inclusion can have positive probability.

Electrical reciprocity makes $K$ symmetric. The two-edge case therefore givesThus edge inclusions are negatively correlated.^[ref] The positive-weight version uses the corresponding conductance-normalized transfer current. Every extendable finite forest has positive inclusion probability, since at least one positively weighted spanning tree contains it.

In a finite connected graph with unit edge electrical resistances, orient two edges $e=(a,b)$ and $f=(c,d)$. The transfer current $K(e,f)$ is the signed current through $f$ when one unit of electric current is injected at $a$ and removed at $b$. If $\varphi$ is the resulting vertex potential, Ohm's law giveswhere $L$ is the graph Laplacian. Potentials are determined up to an additive constant, which cancels in the difference.

On a unit-resistance triangle, injecting across one edge sends $2/3$ of the current along that edge and $1/3$ along the two-edge alternative path. Thus $K(e,e)=2/3$. The transfer-current theorem identifies this diagonal value with the probability that the edge belongs to a uniform spanning tree; exactly two of the triangle's three spanning trees contain it.

Electrical reciprocity makes the unit-resistance kernel symmetric. Reversing one edge orientation changes the appropriate sign, while the determinants giving joint tree-edge probabilities remain unchanged.^[ref]

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 a finite electrical network with positive electrical conductances $c_e$, choose a spanning tree with lawThe one-edge case of the transfer-current theorem gives $\mathrm{Pr}(e\in T)=c_e{R}_{\mathrm{eff}}(a,b)$ for $e=\{a,b\}$. A unit injected electric current produces voltage $R_{\mathrm{eff}}(a,b)$, and Ohm's law makes the electric current along $e$ equal to $c_e{R}_{\mathrm{eff}}(a,b)$.

In a triangle of unit resistors, one resistor is parallel to a series pair, so $R_{\mathrm{eff}}=1\cdot 2/(1+2)=2/3$. Each edge consequently has inclusion probability $2/3$, also clear from the three equally likely spanning trees. For a wired uniform spanning forest, take the finite wired limit and use 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 samples a uniform spanning tree of a finite connected graph by running a simple random walk from any initial vertex. Whenever the random walk first visits a new vertex, retain the edge by which it arrived. Stop when every vertex has been visited.

Each retained edge joins a previously unseen vertex to the already visited connected subgraph. It cannot create a graph cycle; at termination the retained edges form a spanning tree. The stopping time is the cover time, finite almost surely. The nontrivial conclusion is that every spanning tree has exactly the same probability, independently of the starting vertex.^[ref]

Repeated visits add no edges, which can make the method slow when only a few unvisited vertices remain. Wilson's algorithm instead attaches loop-erased random walks. On a recurrent infinite connected graph, the first-entrance construction continues indefinitely and gives the corresponding infinite-volume uniform spanning tree.

For a finite connected graph, Wilson's algorithm starts with a chosen root as the current tree. Choose an unvisited vertex, run a random walk until it hits the current tree, erase loops in chronological order, and attach the resulting simple path. Repeat until every vertex belongs to the tree.

Each attached path has no repeated vertices and first meets the old tree at its endpoint, so attachment preserves connectedness and cannot create a graph cycle. Finiteness and connectedness make each hitting time finite almost surely. The output is a uniform spanning tree, and its law does not depend on the order in which starting vertices were chosen.

For positive electrical conductances $c_{xy}$, use transition probabilities $c_{xy}/{\sum }_z{c}_{xz}$. The output then has probability proportional to ${\prod }_{e\in T}{c}_e$. The proof uses cycle popping: independent stacks of prospective outgoing edges can be exposed and cyclic choices discarded in any order without changing the final rooted tree.^[ref]

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.

For a locally finite connected graph with positive electrical conductances, the number of trees in its wired uniform spanning forest is almost surely a deterministic constant, possibly infinite. A precise characterization uses independent random walks with the conductance transition probabilities. Let $\alpha (w_1,\dots ,w_k)$ be the probability that their full vertex ranges are pairwise disjoint. ThenThe right side depends only on the electrical network. The proof amplifies positive disjointness probability to probabilities arbitrarily close to one, then uses Wilson's algorithm rooted at infinity to obtain at least $k$ components. Conversely, $k$ distinct components force starting vertices admitting positive disjointness probability. This establishes the constant without treating component count as automatically invariant under finite edge changes.^[ref]

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$.