Rooted Trees, Parents, and Children

A Root Adds Structure to a Tree

A tree has no preferred starting point: its vertices and edges alone do not distinguish one vertex from another. Choosing a root adds that distinction and organizes the tree into relationships that resemble a hierarchy. Once the root is fixed, every other vertex has a unique vertex immediately before it on the route from the root. This gives the notions of parent, child, ancestor, descendant, and leaf.

Throughout, graphs are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. A tree is a connected graph with no cycle. We will use the fact that there is exactly one path between any two vertices of a tree; the short proof below also explains why root-based relationships are unambiguous.

For any vertex \(v\), the unique path from \(r\) to \(v\) is called the root-to-\(v\) path. When \(v=r\), this path has no edges. If \(v\ne r\), the vertex immediately before \(v\) on that path is its parent. A vertex \(w\) is a child of \(v\) exactly when \(v\) is the parent of \(w\). Thus the root has no parent, and every other vertex has exactly one parent.

“Proper” matters: a vertex is not counted as its own proper ancestor or proper descendant. The root has no proper ancestors, while every other vertex has at least one. A leaf is defined by its number of children, not simply by its degree in the unrooted graph. For example, a root can have degree one and still have a child, so it need not be a leaf.

Why the Root Determines the Relationships

Proof. Let \(x\) and \(y\) be vertices of a tree \(T\). Since \(T\) is connected, there is a walk from \(x\) to \(y\); deleting any repeated-vertex portions gives a path, so at least one path exists. To prove uniqueness, suppose there are two different paths from \(x\) to \(y\). Follow them from \(x\) until they first diverge, then follow one of them until it first meets the other again. The two portions between the divergence and meeting vertices have no shared internal vertices, and together form a cycle. This contradicts that \(T\) has no cycles. Therefore the path is unique. \(\square\)

Proof. For a vertex \(v\ne r\), the unique root-to-\(v\) path has a vertex immediately before \(v\); call it \(p\). This makes \(p\) a parent of \(v\). Any parent of \(v\) must be the vertex immediately before \(v\) on a root-to-\(v\) path, and that path is unique, so \(p\) is the only parent.

Now consider an edge \(uv\). If \(v\) lies on the root-to-\(u\) path, then the portion of that path from \(v\) to \(u\), together with edge \(uv\), would form a cycle unless \(v\) immediately precedes \(u\). Hence in this case \(v\) is the parent of \(u\). If \(v\) does not lie on the root-to-\(u\) path, appending edge \(uv\) to that path gives a path from \(r\) to \(v\). By uniqueness, it is the root-to-\(v\) path, so \(u\) is the parent of \(v\). Thus every edge joins a parent and a child. \(\square\)

The same structure gives a consistent way to direct the edges. An orientation chooses one direction for each undirected edge. The root-preserving orientation directs every edge from its parent toward its child. In this orientation, the root has indegree zero and every other vertex has indegree one, where indegree is the number of directed edges entering a vertex. Conversely, these indegree conditions identify the root-preserving orientation when the underlying graph is a tree.

Proof. If every edge is directed from parent to child, the root has no parent and therefore no entering edge. Each other vertex has exactly one parent, so exactly one edge enters it. This proves one direction, including the one-vertex case, where there are no edges.

For the converse, assume the stated indegrees. Start at any vertex \(v\ne r\) and repeatedly follow the unique entering edge backwards to its tail. This process cannot continue indefinitely because \(T\) is finite. It cannot revisit a vertex: a revisit would give a directed cycle, and hence a cycle in the underlying tree. It must therefore stop at a vertex with indegree zero. By the assumptions, that vertex is \(r\). Reversing the sequence gives a directed path from \(r\) to \(v\). Since every edge is on the unique path between its endpoints and the orientation directs each vertex’s incoming edge from its parent, all edges point away from \(r\). For \(T\) consisting only of \(r\), the conclusion holds vacuously. \(\square\)

Reading Parent, Ancestor, and Leaf Relationships

Descendants Form a Subtree

Proof. Let \(S\) consist of \(v\) and its proper descendants. If \(x\in S\) and \(x\ne v\), then the root-to-\(x\) path contains \(v\). The portion of that path from \(v\) to \(x\) consists entirely of descendants of \(v\), together with \(v\). Thus every vertex of \(S\) can be joined to \(v\) using vertices of \(S\), so the induced subgraph \(T[S]\) is connected. It has no cycle, because any cycle in \(T[S]\) would also be a cycle in \(T\). Hence \(T[S]\) is a tree. If \(S=\{v\}\), the induced subgraph is the one-vertex tree, so the conclusion still holds. \(\square\)

This result makes “the branch below \(v\)” precise: it includes \(v\), all of its descendants, and every edge of \(T\) whose endpoints lie in that set. The induced-subgraph condition matters. It includes all such edges, not just the parent-child edges selected in a particular description.

A Useful Finite-Tree Consequence

Proof. Start at any vertex \(v\). If it has a child, move to one of its children; continue in this way as long as the current vertex has a child. No vertex can be visited twice, because the parent-child steps would then give a cycle in the underlying tree. Since the tree has finitely many vertices, the process stops at a vertex \(w\) with no children. By definition, \(w\) is a leaf. The sequence from \(v\) to \(w\), preceded by the root-to-\(v\) path, is a root-to-leaf path: the root-to-\(v\) path followed by the chosen child steps has no repeated vertex, since a repeat would again give a cycle. Taking \(v=r\) shows that at least one leaf exists. This also covers the one-vertex tree, where the process stops immediately at its root. \(\square\)

Common Pitfalls

Wrong calculation: “A leaf is any vertex of unrooted degree one, so in the path \(1-2-3\) rooted at \(1\), both \(1\) and \(3\) are leaves.” This uses the wrong criterion. The root \(1\) has one child, namely \(2\), so it is not a leaf under the rooted-tree definition. Vertex \(3\) has no children and is the only leaf. In the one-vertex tree, the root has no children and is a leaf, even though its unrooted degree is zero.

Another common error is to list only immediate neighbors when asked for descendants. A child is an immediate relation; a proper descendant can be several parent-child steps away. In the first example, \(g\) is a proper descendant of \(b\), although \(g\) is not a child of \(b\). Finally, changing the root does not change the underlying edges or turn the graph into a different unrooted tree, but it can change every parent-child relation and which vertices count as leaves.