# Chapter 10. Trees # Chapter 10. Trees A tree is a connected graph with no cycles. Trees are among the most important structures in graph theory because they combine two properties that strongly constrain structure: 1. Every pair of vertices is connected. 2. No closed path exists. These conditions make trees sparse, hierarchical, and easy to analyze. Trees appear in algorithms, file systems, parsing, routing, optimization, databases, compilers, phylogenetics, and many other areas. ## 10.1 Definition of a Tree A **tree** is a connected acyclic graph. Equivalently, a graph \(T\) is a tree when: 1. \(T\) is connected. 2. \(T\) contains no cycle. For example, the graph with vertex set $$ V=\{a,b,c,d,e\} $$ and edge set $$ E= \{\{a,b\},\{a,c\},\{c,d\},\{c,e\}\} $$ is a tree. The graph is connected because every pair of vertices is joined by a path. It is acyclic because no cycle exists. Trees form the basic connected structures without redundancy. ## 10.2 Forests A **forest** is an acyclic graph. Thus every connected component of a forest is a tree. A forest may be disconnected. A tree is exactly a connected forest. For example, the graph $$ E= \{\{a,b\},\{b,c\},\{d,e\}\} $$ is a forest with two components: $$ \{a,b,c\} $$ and $$ \{d,e\}. $$ Each component is a tree. ## 10.3 Basic Examples Several standard graph families are trees. | Graph | Tree? | Reason | |---|---|---| | Path graph \(P_n\) | Yes | Connected and acyclic | | Cycle graph \(C_n\) | No | Contains a cycle | | Complete graph \(K_n\), \(n \geq 3\) | No | Contains cycles | | Star graph | Yes | Connected and acyclic | | Empty graph on one vertex | Yes | Connected and acyclic | The simplest nontrivial tree is $$ P_2, $$ a graph with two vertices and one edge. ## 10.4 Unique Path Property One of the central properties of trees is uniqueness of paths. ### Theorem A graph \(T\) is a tree if and only if every pair of distinct vertices is joined by exactly one path. ### Proof Suppose \(T\) is a tree. Because \(T\) is connected, at least one path joins every pair of vertices. Suppose two distinct paths joined vertices \(u\) and \(v\). Traversing one path from \(u\) to \(v\) and returning along the other would create a cycle. This contradicts acyclicity. Therefore exactly one path joins every pair of vertices. Conversely, suppose every pair of vertices is joined by exactly one path. Then the graph is connected. If a cycle existed, then two distinct paths would connect some pair of vertices on the cycle. This contradicts uniqueness. Hence the graph is acyclic and therefore a tree. This theorem characterizes trees through path structure rather than directly through cycles. ## 10.5 Trees Have Few Edges Trees are sparse graphs. ### Theorem If a tree \(T\) has \(n\) vertices, then it has exactly $$ n-1 $$ edges. ### Proof The proof proceeds by induction on \(n\). If $$ n=1, $$ then the tree consists of one vertex and no edges, so the formula holds. Assume every tree with \(n-1\) vertices has \(n-2\) edges. Let \(T\) be a tree with \(n\) vertices. Since \(T\) is finite and acyclic, it contains a leaf. Remove a leaf \(v\) and its incident edge. The remaining graph is still a tree. It has $$ n-1 $$ vertices, so by induction it has $$ n-2 $$ edges. Restoring the removed edge gives $$ n-1 $$ edges in total. Thus every tree with \(n\) vertices has exactly $$ n-1 $$ edges. This formula is one of the defining numerical properties of trees. ## 10.6 Leaves A **leaf** is a vertex of degree \(1\). Leaves occur naturally at the outer boundary of a tree. ### Theorem Every tree with at least two vertices has at least two leaves. ### Proof Let $$ v_0,v_1,\ldots,v_k $$ be a longest path in the tree. Suppose \(v_0\) had degree greater than \(1\). Then some edge from \(v_0\) would lead to a vertex not already on the path. Extending the path through that edge would produce a longer path, contradicting maximality. Therefore $$ \deg(v_0)=1. $$ Similarly, $$ \deg(v_k)=1. $$ Thus both endpoints are leaves. This theorem shows that trees always branch outward toward degree-\(1\) vertices. ## 10.7 Equivalent Characterizations of Trees Several different properties characterize trees. ### Theorem For a finite graph \(T\) with \(n\) vertices, the following are equivalent: 1. \(T\) is a tree. 2. \(T\) is connected and has \(n-1\) edges. 3. \(T\) is acyclic and has \(n-1\) edges. 4. Every pair of vertices is joined by exactly one path. 5. \(T\) is connected, and removing any edge disconnects it. 6. \(T\) is acyclic, and adding any new edge creates exactly one cycle. These equivalent forms are fundamental in graph theory. Different proofs and algorithms naturally use different characterizations. ## 10.8 Minimal Connected Graphs Trees are minimal connected graphs. If any edge is removed from a tree, the graph becomes disconnected. ### Proof Let $$ e=\{u,v\} $$ be an edge of a tree \(T\). Since \(T\) has exactly one path between any two vertices, the edge \(e\) lies on the unique path between \(u\) and \(v\). Removing \(e\) destroys that path. Therefore \(u\) and \(v\) become disconnected. Hence every edge of a tree is a bridge. This property shows that trees contain no redundant edges. ## 10.9 Maximal Acyclic Graphs Trees are maximal acyclic graphs. If an edge is added between two nonadjacent vertices of a tree, exactly one cycle is created. ### Proof Let \(u\) and \(v\) be nonadjacent vertices of a tree \(T\). Because \(T\) is connected, a unique path joins \(u\) and \(v\). Adding the edge $$ \{u,v\} $$ creates a closed walk consisting of that path plus the new edge. This produces exactly one cycle, because no cycle existed previously. Thus trees are acyclic graphs that become cyclic immediately when any extra edge is added. ## 10.10 Rooted Trees A **rooted tree** is a tree with one distinguished vertex called the **root**. The root introduces hierarchy and direction. If \(r\) is the root, then every vertex except \(r\) has a unique parent: the previous vertex on the unique path from \(r\). Vertices connected downward from a vertex are called its children. For example: ```text id="4o8l9q" r / | \ a b c | d ``` Here: - \(r\) is the root. - \(a,b,c\) are children of \(r\). - \(d\) is a child of \(b\). Rooted trees appear in syntax trees, file systems, heaps, search trees, and recursive structures. ## 10.11 Parent, Child, and Sibling Relations In a rooted tree: - The parent of \(v\) is the preceding vertex on the path from the root. - A child of \(u\) is a vertex whose parent is \(u\). - Vertices with the same parent are siblings. These relations convert the tree into a hierarchical structure. If $$ u $$ is above $$ v $$ on the root path, then \(u\) is an ancestor of \(v\), and \(v\) is a descendant of \(u\). ## 10.12 Levels and Height The **level** or **depth** of a vertex is its distance from the root. The root has depth \(0\). The **height** of a rooted tree is the maximum depth of any vertex. For example: ```text id="wx4dy8" r / \ a b / \ c d ``` The depths are: | Vertex | Depth | |---|---:| | \(r\) | 0 | | \(a\) | 1 | | \(b\) | 1 | | \(c\) | 2 | | \(d\) | 2 | The tree height is \(2\). Tree height measures the longest root-to-vertex path. ## 10.13 Binary Trees A **binary tree** is a rooted tree in which every vertex has at most two children. The children are often distinguished as left and right children. Binary trees are central in computer science because they support recursive decomposition and efficient search structures. Examples include: | Structure | Description | |---|---| | Binary search tree | Ordered search structure | | Heap | Priority queue structure | | Expression tree | Arithmetic expression representation | | Huffman tree | Prefix coding structure | A **full binary tree** is a binary tree in which every internal vertex has exactly two children. ## 10.14 Spanning Trees Let $$ G $$ be a connected graph. A **spanning tree** of \(G\) is a subgraph of \(G\) that: 1. Contains every vertex of \(G\). 2. Is a tree. A spanning tree preserves connectivity while removing cycles. For example, if \(G\) is a cycle graph $$ C_4, $$ then removing any one edge produces a spanning tree. Every connected graph has at least one spanning tree. ## 10.15 Constructing Spanning Trees A spanning tree can be constructed by repeatedly removing edges from cycles while preserving connectivity. Alternatively, breadth-first search and depth-first search naturally generate spanning trees. A BFS spanning tree records shortest-path structure from the starting vertex. A DFS spanning tree records recursive exploration structure. Spanning trees are fundamental in routing, network design, optimization, and graph algorithms. ## 10.16 Cayley's Formula The number of distinct labeled trees on \(n\) vertices is $$ n^{n-2}. $$ This result is called **Cayley's formula**. For example: | \(n\) | Number of labeled trees | |---:|---:| | 1 | 1 | | 2 | 1 | | 3 | 3 | | 4 | 16 | | 5 | 125 | Cayley's formula is one of the classical counting results in combinatorics. It shows that even though trees are sparse, the number of possible tree structures grows rapidly. ([en.wikipedia.org](https://en.wikipedia.org/wiki/Cayley%27s_formula?utm_source=chatgpt.com)) ## 10.17 Tree Traversals Traversal algorithms systematically visit the vertices of a tree. Common traversals include: | Traversal | Strategy | |---|---| | Preorder | Visit node before children | | Inorder | Visit left subtree, node, right subtree | | Postorder | Visit children before node | | Level-order | Visit vertices by depth | These traversals are especially important for rooted and binary trees. For example, expression trees use postorder traversal for evaluation and inorder traversal for symbolic display. ## 10.18 Example Let $$ V=\{a,b,c,d,e,f\} $$ and $$ E= \{\{a,b\},\{a,c\},\{b,d\},\{b,e\},\{c,f\}\}. $$ The graph is connected. The graph has $$ 6 $$ vertices and $$ 5 $$ edges. Since $$ 5 = 6-1, $$ it satisfies the tree edge formula. No cycle exists, so the graph is a tree. The leaves are $$ d,e,f. $$ The unique path from \(d\) to \(f\) is $$ d,b,a,c,f. $$ Removing the edge $$ \{a,c\} $$ disconnects the graph. Adding the edge $$ \{d,f\} $$ creates exactly one cycle. ## 10.19 Summary A tree is a connected acyclic graph. Trees have exactly $$ n-1 $$ edges, contain unique paths between vertices, and become disconnected when any edge is removed. Forests are acyclic graphs whose components are trees. Rooted trees introduce hierarchy through parent-child relations. Binary trees restrict each vertex to at most two children. Trees are minimal connected graphs and maximal acyclic graphs. They appear throughout graph theory, combinatorics, algorithms, optimization, and computer science because they provide the simplest possible connected structures.