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:

Every pair of vertices is connected.
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:

$T$ is connected.
$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$ .

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:

$T$ is a tree.
$T$ is connected and has $n-1$ edges.
$T$ is acyclic and has $n-1$ edges.
Every pair of vertices is joined by exactly one path.
$T$ is connected, and removing any edge disconnects it.
$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:

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.

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:

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:

Contains every vertex of $G$ .
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)

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.