Rooted tree

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.

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.