Tree

A tree is a connected graph containing no cycle. A finite tree on $n$ vertices has $n-1$ edges.

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.

A rooted tree is a tree with a distinguished vertex called the root. Its levels consist of the vertices at a fixed graph distance from the root.

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.

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 a graph containing no cycle; each of its connected components is a tree.

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 spanning tree of a connected graph is a tree containing every vertex of the graph.

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.

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

Cayley's formula says that there are $n^{n-2}$ trees on a fixed set of $n$ labelled vertices.

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 explores a graph in successive distance layers from a starting vertex. Before two exploration branches meet, the explored edges form a tree.