Tree (graph theory)

A tree is a nonempty connected graph containing no graph cycle. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite simple graph with $n\ge 1$ vertices, three descriptions are equivalent: being a tree; having exactly one simple graph path between every pair of distinct vertices; and being a connected graph with exactly $n-1$ edges. Here a simple graph path repeats no vertex. Connectedness in the last description is essential. ^[ref]

For a concrete tree, label the vertices $1,\dots ,7$ and take the edgeswhere $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven vertices and six edges. The unique graph path from $4$ to $7$ is $4,2,1,3,6,7$, using five edges. The degree sequence in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot 6$, as the degree-sum formula predicts. Each of $4,5,7$ is a leaf of a graph, having vertex degree one.

Deleting edge $13$ leaves precisely two connected components of a graph, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every edge of a tree is a bridge in a graph. Instead add edge $57$ to the original tree: it closes the unique existing graph path $5,2,1,3,6,7$ into exactly one graph cycle. Thus a tree provides economical connections with no redundancy: a single failed link separates locations. Every finite tree with at least two vertices has at least two instances of a leaf of a graph; the endpoints of a longest graph path supply them. ^[ref]

The number $n-1$ alone proves nothing about connectedness: a cycle graph on $1,\dots ,6$ together with an isolated vertex $7$ has seven vertices and six edges, yet is disconnected. Briefly, two different simple graph paths between the same vertices would contain a graph cycle. Repeatedly removing a leaf of a graph and its incident edge proves the tree count $n-1$ by mathematical induction, starting with one vertex and no edges.

A nonempty connected subgraph of a tree. Between any two included vertices, it contains the unique tree path: its connectedness supplies a path, and the ambient tree has only one. Such subgraphs satisfy the Helly property. They need not contain every descendant of an included vertex in any chosen rooting, unlike the descendant-closed data-structure subtree convention.

A finite family of nonempty connected subgraphs of a tree with pairwise nonempty intersections has a common vertex. For a finite ambient tree, prove this by deleting a leaf of a tree $v$. If one member is $\{v\}$, pairwise intersection proves the result immediately. Otherwise remove $v$ from every member containing it. Each such member remains nonempty and connected and contains the unique neighbour of $v$. Hence every pair still intersects, even if its original intersection consisted only of $v$, and mathematical induction applies. This is the Helly property specialized to trees.

A tree together with an embedding in an oriented plane, considered up to deformation preserving the cyclic order of incident edges. For a rooted plane tree, the embedding orders the children of each vertex.

A plane tree with a distinguished root and root corner, equivalently a rooted tree with a linear order on the children at each vertex. Trees with $n$ edges are counted by the Catalan number $C_n$.

A lobster tree is a tree whose removal of all leaves leaves a caterpillar tree.

The dissymmetry theorem for trees relates unrooted trees to trees rooted at a vertex, at an edge, and at a directed edge. In the corresponding counting identity, unrooted equals vertex-rooted plus edge-rooted minus directed-edge-rooted.

A tree whose vertices carry distinct labels from a fixed finite set, as a labelled combinatorial structure. Two labelled trees on the same vertex set are equal when their sets of edges are equal: any comparison must keep every label fixed. Cayley's formula counts these trees.

A tree considered up to graph isomorphism, with vertex names ignored. For example, all four labelled trees that are star graphs on $\{1,2,3,4\}$ represent one unlabelled tree. Dividing the total in Cayley's formula by $n!$ does not count unlabelled trees: different shapes can have different numbers of distinct labellings.

An infinite connected tree is regular of degree $k$ if every vertex has exactly $k$ neighbours. Necessarily $k\ge 2$. For $k=2$ it is a two-sided infinite path. For $k\ge 3$, rooting it gives $k$ children at the root and $k-1$ children at each other vertex; this constructs the unique such tree up to graph isomorphism.

For a nonempty finite vertex set $A$ in a degree-$k$ regular tree, its induced forest has $|A|-c(A)$ edges, where $c(A)$ counts its components. Summing degrees and subtracting twice the internal edge count gives the displayed number of edges with exactly one endpoint in $A$. In particular it is at least $(k-2)|A|+2$.

An oriented tree is an orientation of every edge of an undirected tree. Its arrows need not all point towards, or away from, any one root. It is acyclic as a directed graph, but different orientations can have different embedding behaviour in tournaments.

For a source-rooted oriented tree, let $b$ count edges pointing towards the root and let $c$ count nonempty connected components formed by those edges. A half-sparse median-order embedding exists in $2n+2(b-c)$ vertices. Remove forward leaves, or remove a terminal backward component of order $m$ and replace it temporarily by $2m-2$ outward leaves. Their images contain an in-arborescence copy of the component. Choose the direction and root to minimize $(b-c,b)$ lexicographically; this makes the root a source and gives $b-c\le (n-3)/2$ unless the tree is already an arborescence. The stated bound follows.

An arborescence is a rooted oriented tree whose edges all point away from its root. Reversing every edge gives an in-arborescence. An $n$-vertex arborescence embeds in every tournament on $2n-2$ vertices: repeatedly extend an outward leaf in a half-sparse median-order embedding. Reversal gives the analogous existence statement for in-arborescences.

A depth-first traversal starts at a root, recursively visits each child subtree, and returns along the entering edge. On a finite tree, the resulting closed walk traverses each edge exactly once in each direction.

Visit all child subtrees before visiting their parent. A depth-first traversal of a tree produces this order by processing a node on return from its recursive calls. It lets dynamic programming use the already computed answers of every child subtree.

Visit a rooted tree's root before recursively visiting its child subtrees in their specified order. For a binary tree, the order is root, left subtree, right subtree. Unlike inorder traversal, this interpretation stores an internal node's label before either child's labels.

A rooted tree is a tree with a distinguished vertex, its root of a tree $r$. Choosing $r$ turns connections into a hierarchy: every other vertex has a unique parent in a rooted tree, the preceding vertex on its graph path from $r$. Conversely, the vertices whose parent in a rooted tree is $v$ are the children in a rooted tree of $v$. Choosing the root of a tree changes this description, while the underlying edges remain the same. Arrows towards the root of a tree can encode the relationship, as in MIT's counting notes; the undirected tree itself needs no arrows. ^[ref]

In the seven-vertex tree above, choose $r=1$. The levels, grouped by graph distance from the root of a tree, are $\{1\}$, $\{2,3\}$, $\{4,5,6\}$, $\{7\}$. The children in a rooted tree of $2$ are $4,5$, and the parent in a rooted tree of $7$ is $6$. Choosing $r=7$ instead makes the levels $\{7\}$, $\{6\}$, $\{3\}$, $\{1\}$, $\{2\}$, $\{4,5\}$: now $6$ has parent in a rooted tree $7$, reversing their relationship. All six edges survive.

This hierarchy supports structural recursion: process the smaller rooted trees below each vertex, then combine their results. A depth-first traversal of a tree explores one branch before returning; breadth-first search processes successive levels. The lowest common ancestor identifies where two routes from the root of a tree last coincide. For $4,5$ it is $2$ when $r=1$. A binary tree imposes an additional restriction on children in a rooted tree; a general rooted tree has no such bound.

A rose tree is an ordered rooted tree in which each vertex can have any finite number of children in a rooted tree. A labelled Haskell representation is data RTree a = Node a [RTree a]. Its tree fold has type (a -> [b] -> b) -> RTree a -> b: recursively fold the children, then combine their results with the current label. Unlike a binary tree, a rose tree has no fixed pair of child positions.

A rose tree is perfect when all its leaves of a rooted tree have the same depth. This permits unequal branching counts and unary branches; perfectness alone does not require every internal vertex to have the same number of children. A bottom-up certificate returns Just 0 at a leaf, Just (h+1) when all child certificates are Just h, and Nothing otherwise. Structural induction proves that a certificate exists exactly when the tree is perfect: all root-to-leaf routes acquire one edge when attached to the new root.

A vertex reachable from a specified vertex by following child edges in a rooted tree. Allowing the length-zero graph path includes the starting vertex; a proper descendant excludes it. The subtree at a vertex consists of that vertex and its descendants. State the properness convention when using strict discovery-time inequalities.

Two distinct vertices are siblings when they have the same parent in a rooted tree.

A vertex with at least one child in a rooted tree. Internal vertices and leaves of a rooted tree partition the vertex set. The ancestors of an internal vertex are also internal; consequently the internal vertices of a nontrivial rooted tree induce a connected subgraph containing its root.

A node with no children in a rooted tree. This depends on the chosen root: the root of a nontrivial tree can have undirected vertex degree one while still having a child and therefore not being a leaf in the rooted sense. In a single-node rooted tree, the root is a leaf. The distinction matters when counting the complement of the internal vertices of a rooted tree.

A rooted tree in which every internal vertex has exactly three tree children. For a finite rooted tree with $m$ tree leaves and internal outdegrees $d_v$, counting edges in two ways givesIndeed, the number of edges is the total number of vertices minus one and also the sum of the internal outdegrees. Thus a full ternary tree with $N$ internal vertices has $m=1+2N$ tree leaves, always an odd number. More generally, if every internal vertex has either two or three tree children, $m=1+N_2+2N_3$. This parity controls the initial merge in ternary Huffman coding.

A full ternary tree whose leaves all have the same depth. At depth $j$ there are $3^j$ vertices, so a tree with $h+1$ levels has $N_h={\sum }_{j=0}^h{3}^j=(3^{h+1}-1)/2$ vertices and $3^h$ leaves, by the finite geometric series formula. For a rose tree representation, recursively flattening children and joining their lists with ordinary list concatenation copies each label once per ancestor. The work is therefore $\Theta ((h+1)3^h)=\Theta (N_h\log N_h)$ when the complete output is demanded. Passing an already constructed suffix through the recursion instead emits each label once, giving $\Theta (N_h)$ work.

The distinguished vertex that specifies a rooted tree. Its choice determines the parent in a rooted tree and children in a rooted tree relationships.

For a nonroot vertex, its adjacent predecessor on the unique graph path from the root of a tree. The root of a tree has no parent.

A vertex whose parent in a rooted tree is the specified vertex.

The exponential generating function for labelled rooted trees satisfies $T=z{e}^T$: remove the root and obtain an unordered set of smaller labelled rooted trees. For $0\le z<1/e$, the convergent series is the solution in $[0,1)$ of $T{e}^{-T}=z$, rather than the larger real solution. Alternatively, tree-component expectation in the Erdős-Rényi model and subcritical exploration give $T(\theta e^{-\theta })=\theta$ for $0<\theta <1$: their limiting probabilities for the order of the tree component of a uniform vertex sum to one. The component tail bound makes this passage through the infinite sum valid.

For finite rooted trees in the ancestor partial order, a rooted-tree homeomorphic embedding is an injective vertex map preserving lowest common ancestors: $h(u\wedge v)=h(u)\wedge h(v)$. The image of the source root need not be the host root. Edge paths and branching are preserved, while paths may be subdivided in the larger tree.

Give a leaf rank zero, and use Hessenberg natural sum over the immediate rooted subtrees. Every rank is below epsilon zero; conversely repeated exponentiation and finite summation encode every Cantor normal form below it. A rooted-tree homeomorphic embedding implies nondecrease of the rank. When roots match, child subtrees embed into distinct branches and exponentiation and natural sum preserve their inequalities. When the source root maps below the host root, its rank is bounded by that of a proper subtree, strictly below the host rank.

An adjacency-preserving rooted-tree embedding is an injective vertex map preserving the root and every adjacency. Because each root-to-vertex path maps to a simple path of the same length, vertex depths are preserved. This is more restrictive than a homeomorphic embedding of a rooted tree, which may stretch edges into paths. The branching-depth antichain of rooted trees shows that the adjacency relation is not a well-quasi-ordering.

Let $T_m$ consist of a rooted path of $m\ge 1$ edges followed by two leaves at its far end. Its only vertex with two children has depth $m$. An adjacency-preserving rooted-tree embedding must preserve this depth, so $T_m$ embeds into $T_n$ only when $m=n$. This gives an infinite bad sequence, while rooted-tree homeomorphic embeddings can stretch the stems.

For rooted trees labelled in a preorder $Q$, a label-monotone tree embedding is a homeomorphic embedding of a rooted tree whose vertex map satisfies ${\ell }_T(v){\le }_Q{\ell }_S(h(v))$. The root need not map to the host root. For ordered child lists, require in addition that the map preserve the relative order of distinct branches.

The lowest common ancestor of two vertices is the common ancestor farthest from the root. In the ancestor partial order with the root least, it is their infimum, also called their greatest common ancestor.

For a label set $D$, define $\mathcal{T}(D)$ inductively: choose a root label $d\in D$ and a finite repetition-free sequence of rooted trees in $\mathcal{T}(D\setminus \{d\})$ as its children. Each object is a finite ordered rooted tree. Labels are distinct along each root-to-leaf path, and child rooted trees at a vertex are distinct as whole rooted trees. Labels may repeat across different branches; children need not have distinct root labels. For a finite pool of size $m$, the exact number $t_m$ of rooted trees satisfiesThis follows by choosing the root and then an ordered repetition-free list from the finite pool of smaller rooted trees.

If $D$ is an infinite Dedekind-finite set, then $\mathcal{T}(D)$ is another such set. Single-vertex rooted trees inject $D$ into it. A countable sequence of distinct rooted trees gives finite lists of labels by the depth-first traversal of a tree in the prescribed child order. By countable union of explicitly ordered finite lists without choice, an infinite union of labels contradicts Dedekind-finiteness. A finite union $F$ is equally impossible, since every rooted tree then lies in the finite set $\mathcal{T}(F)$, by mathematical induction on $|F|$ using the recursive child rule. Thus no countably infinite subset of rooted trees exists.

For an automorphism $g$ of a regular rooted tree and a first-level vertex $i$, the section $g_i$ is the induced automorphism of the rooted subtree at $i$, defined byAn automorphism fixing the first level is determined by the tuple of all its sections.

A forest is an undirected graph with no graph cycle; each of its connected components of a graph is a tree, including any isolated vertex. A finite forest with $n$ vertices and $c$ connected components of a graph hasIndeed, a connected component of a graph with $n_i$ vertices contributes $n_i-1$ edges; adding these counts gives $n-c$. Equivalently, start with $n$ isolated vertices: every added edge must join different connected components of a graph, reducing their number by one. Joining vertices already connected would create a graph cycle. ^[ref]

Deleting $13$ in our example gives $n=7$, $c=2$, and five edges: the two trees contribute $3+2=5=7-2$. Deleting $67$ as well leaves $7$ isolated, so $c=3$ and four edges. A forest therefore describes separate hierarchies or the intermediate stages of building a spanning tree. The acyclic graph condition accounts for missing connections without assuming that all locations are mutually reachable.

A forest whose connected components of a graph are star graphs. In an inclusion-minimal edge cover, every edge has at least one endpoint of vertex degree one, forcing this structure with no isolated vertex.

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.

A forest containing one minimum spanning tree of each connected component of a graph of a finite undirected weighted graph, including isolated vertices. For disconnected input, Kruskal's algorithm returns a minimum spanning forest.

Among all acyclic graphs contained in a finite weighted undirected graph, with no requirement to connect vertices, one optimum is obtained by keeping only strictly negative edges and computing their minimum spanning forest. Removing a nonnegative edge never worsens weight or creates a cycle. Within a connected component of the negative-edge subgraph, any disconnected candidate forest can be extended by a negative crossing edge, strictly improving its weight. Hence an optimum must span each such component and minimise its tree weight. Kruskal's algorithm on the negative edges therefore solves the problem. Zero-weight edges are optional when they preserve acyclicity.

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

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.

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.

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.

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

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

For a fixed set of $k<n$ roots among $n$ labelled vertices, the number of forests with exactly one root in each graph component is $k{n}^{n-k-1}$. Orient edges toward their roots. Repeatedly remove the smallest nonroot leaf and record its parent. This gives a code of length $n-k$ whose last entry is a root. Conversely, for any such code choose the smallest remaining nonroot absent from the remaining code, join it to the first entry, and delete it. There is always a choice because the final entry is a root. These inverse operations give $n^{n-k-1}$ choices for the earlier entries and $k$ for the last. For $k=n$, the empty forest is unique.

For $n\ge 2$, a Prüfer sequence is the encoding of a labelled tree on $\{1,\dots ,n\}$ by a sequenceRepeated labels are allowed, and their order matters. To encode the tree, repeatedly remove its smallest-labelled leaf of a graph together with its incident edge, recording the label of its unique neighbour. Stop when two vertices remain; do not record their final edge. Removing a leaf of a graph leaves a tree, so the procedure makes exactly $n-2$ deletions. The choice of the smallest label makes the encoding deterministic. ^[ref]

For a concrete example, take six vertices and the set of edgesInitially $2,4,6$ label the vertices of vertex degree one. Remove $2$ and record its neighbour $1$. Now $1$ has become a leaf of a graph, so remove $1$ and record $3$. Next remove $4$ and record $3$ again; then remove $3$ and record $5$. The final edge joins $5$ and $6$. Thus the Prüfer sequence isThe deletion order is $2,1,4,3$: removing a leaf of a graph can make its neighbour a leaf of a graph, so the eligible labels change as the tree shrinks.

To decode, keep a set $L$ of remaining labels, initially $\{1,\dots ,n\}$, and the remaining sequence, initially $p$. While the sequence is nonempty, let $v$ be the smallest label in $L$ absent from the entire remaining sequence. Add an edge between $v$ and its first entry, then remove $v$ from $L$ and delete that first entry. Finally join the two labels left in $L$. For the example:

The decoder always has a choice: if the remaining sequence has length $m$, then $L$ has $m+2$ labels, so at least two of them are absent. Its first entry is still in $L$, and differs from the chosen absent label. Every removed vertex attaches to a vertex that survives longer; following these attachments eventually reaches the final pair. Consequently the decoded graph is connected, and its $n-1$ edges make it a tree. In this construction, each occurrence of $v$ contributes an incident edge, and $v$ gets one more edge at its final attachment. Thus a remaining label is absent from the remaining sequence exactly when it labels a leaf of a graph. Encoding and decoding choose the same smallest label at each step and undo each other. This bijection proves Cayley's formula and explains why every freely chosen sequence is valid. ^[ref]

For $n=2$ there is exactly one empty sequence, and decoding adds the sole edge. For $n=1$ there is one tree, with vertex degree zero, but no length-$n-2$ Prüfer sequence. This is the exception both to the encoding convention and to the Prüfer degree formula.

Heinz Prüfer's 1918 paper "Neuer Beweis eines Satzes über Permutationen" appeared in Archiv der Mathematik und Physik, third series, volume 27, pages 142–144. It gives an encoding proof of the labelled tree count. The historical title means "New proof of a theorem on permutations"; the modern Prüfer sequence permits repeated labels, so it is not a permutation. ^[ref]

A tree on $2m+1$ labels has one root of degree two, $m-1$ other interior vertices of degree three, and $m+1$ leaves precisely when its Prüfer code contains one label once, $m-1$ labels twice, and all other labels zero times. The Prüfer degree formula gives both directions, and identifies the root as the uniquely once-occurring label. Children are unordered unless a plane embedding is additional data.

For a labelled tree with $n\ge 2$ vertices, the vertex degree of label $v$ is one plus the number of occurrences of $v$ in its Prüfer sequence:Each recording of $v$ corresponds to an incident edge removed when a neighbouring leaf of a graph is deleted. Exactly one incident edge remains when $v$ itself is deleted, or when it belongs to the final pair. In particular, $v$ is a leaf of a graph exactly when it never occurs in the Prüfer sequence. The same reasoning applies to each remaining tree and its remaining code. ^[ref]

For $p=(1,3,3,5)$, the occurrence counts in label order are $(1,0,2,0,1,0)$, giving the degree sequence $(2,1,3,1,2,1)$. Its sum is $10=2(6-1)$, as required by the degree-sum formula. More generally, summing the occurrence counts gives $n-2$, so summing the vertex degrees gives $n+(n-2)=2(n-1)$.

For $n\ge 2$ and positive integers $d_1,\dots ,d_n$ with ${\sum }_v{d}_v=2(n-1)$, the number of labelled trees having vertex degree $d_v$ at label $v$ isBy the Prüfer degree formula, this is the multinomial coefficient counting sequences with $d_v-1$ occurrences of each label. If a degree is zero or the sum is wrong, there are no such trees. For the example degree sequence $(2,1,3,1,2,1)$, there are $4!/(1!0!2!0!1!0!)=12$ labelled trees, one for each ordering of the labels $1,3,3,5$. Knowing the vertex degrees thus constrains, but usually does not determine, the tree.

For $n\ge 2$, choose $n-2$ independent random variables, each with the uniform distribution on a finite set $\{1,\dots ,n\}$, and decode their values as a Prüfer sequence. Every sequence has probability $n^{-(n-2)}$, and the bijection gives each labelled tree the same probability. This produces a uniform spanning tree of the complete graph without repeatedly proposing sets of edges and rejecting those that fail to be trees. It supplies random inputs for testing implementations of breadth-first search and a tractable model of random connections. ^[ref]

This distribution is uniform over fixed-label trees, rather than over unlabelled trees. With four labels, the star graph shape has probability $4/16=1/4$ and the path graph shape has probability $12/16=3/4$. Also, for a fixed label $v$, the Prüfer degree formula givesHere the binomial distribution counts the independent code positions equal to $v$. The expected value agrees with the average vertex degree from the degree-sum formula. Individual labels have the same distribution by symmetry, though their vertex degrees are constrained together by their fixed sum. When $n=1$, simply return the single isolated vertex.

Every infinite finitely branching rooted tree has an infinite branch. Starting at the root, repeatedly choose a child above which infinitely many vertices remain.

Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex $s$. Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a FIFO queue. Repeatedly remove the front vertex $u$ and scan its adjacency list. Whenever a graph neighbour $v$ is still undiscovered, mark it immediately, record $u$ as its parent in a rooted tree in the discovery tree, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. ^[ref]

Use the same undirected graph as depth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.

The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the FIFO queue is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its parent in a rooted tree unchanged. The discovery edges are $AB,AC,BD,BE,CF,EG$, forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.

First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered vertices receive distance $k+1$ and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of edges from $s$ to $v$. This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives $G,E,B,A$; reverse that sequence to obtain the three-edge graph path $A,B,E,G$. $A,C,F,G$ is another shortest graph path, but the specified graph neighbour order makes $E$ discover $G$ first. Changing that order can change the parent in a rooted tree without changing graph distances. ^[ref]

The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.

With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is $O(|V|+|E|)$ in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes $O(|V|)$. The FIFO queue contains at most $|V|$ vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give $O(|V|)$ auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.

A single start reaches only its connected component of a graph. Unreached vertices retain distance $\infty$ and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original $s$.

The tree search version of breadth-first search explores action histories in nondecreasing length without automatically removing repeated states. A finite branching factor ensures that every finite depth contains finitely many histories, so the method is a complete search algorithm for goals reachable at finite depth. With equal positive action costs it is an optimal search algorithm for total action cost. It need not terminate on an unsolvable instance with an infinite search tree, and it need not optimize a terminal reward unrelated to depth.

Maintain a FIFO queue of child iterators ordered by the breadth-first order of their parents. Consume a child from the front iterator and append a deferred iterator for that child's children; discard empty front iterators as needed. This enumerates descendants without first materializing a whole child list or level. On a locally finite tree, each node occurs after finitely many earlier outputs. If an earlier level is infinite, strict breadth-first order cannot put a deeper node at any finite output position; that obstruction is inherent in the requested ordering.