The Central Idea
A tree combines two properties:
- it is connected;
- it contains no cycle.
Therefore,
\[ \boxed{\text{tree}=\text{connected acyclic graph}}. \]A tree contains enough edges to keep all vertices connected, but no extra edge that would create a cycle.
A First Tree
Let
\[ V=\{a,b,c,d,e\} \]and
\[ E= \bigl\{ \{a,b\},\{a,c\},\{b,d\},\{b,e\} \bigr\}. \]Every vertex is reachable from every other vertex, so the graph is connected.
No cycle appears, so the graph is a tree.
A Tree as a Picture
Trees Have No Cycles
A cycle is a closed route that returns to its starting vertex without repeating another vertex.
A tree contains no such route.
If an extra edge were added between \(c\) and \(d\) in the example above, then
\[ a,b,d,c,a \]would form a cycle, so the resulting graph would no longer be a tree.
Trees Must Be Connected
A graph can be acyclic without being a tree.
For example,
\[ E=\bigl\{\{a,b\},\{c,d\}\bigr\} \]contains no cycle, but the graph is disconnected.
Therefore it is not a tree.
Forests
An acyclic graph that may be disconnected is called a forest.
Each connected component of a forest is a tree.
Thus,
\[ \boxed{\text{forest}=\text{acyclic graph}}. \]Every Two Vertices Have a Unique Path
One of the most important properties of a tree is that every pair of vertices is connected by exactly one path.
If two different paths existed between the same vertices, those paths would combine to create a cycle.
Therefore,
\[ \boxed{\text{in a tree, every pair of vertices has a unique path}}. \]Example: Unique Path
In the running tree, the unique path from \(d\) to \(c\) is
\[ d,b,a,c. \]There is no second route connecting \(d\) and \(c\).
Removing an Edge Disconnects a Tree
Every edge in a tree is structurally necessary for connectivity.
If any edge is removed, the graph becomes disconnected.
For example, removing \(\{a,b\}\) separates
\[ \{b,d,e\} \]from
\[ \{a,c\}. \]Adding an Edge Creates a Cycle
A tree is also maximal with respect to being acyclic.
If we add an edge between two previously nonadjacent vertices, the unique path already joining those vertices combines with the new edge to create exactly one cycle.
Edges and Vertices in a Finite Tree
Every finite tree with \(n\) vertices has exactly
\[ \boxed{n-1} \]edges.
Therefore, if
\[ |V|=n, \]then
\[ \boxed{|E|=n-1}. \]Example: Counting Edges
A tree with \(8\) vertices must have
\[ 8-1=7 \]edges.
\[ \boxed{|E|=7}. \]The Converse Needs Connectivity or Acyclicity
Having \(n-1\) edges alone does not automatically make a graph a tree.
However, either of the following is sufficient:
- a connected graph with \(n\) vertices and \(n-1\) edges is a tree;
- an acyclic graph with \(n\) vertices and \(n-1\) edges is a tree.
Leaves
A leaf is a vertex of degree \(1\) in a nontrivial tree.
In the running tree,
\[ c,\qquad d,\qquad e \]are leaves.
Each is attached to the rest of the tree by exactly one edge.
Internal Vertices
A vertex that is not a leaf is often called an internal vertex.
In the running tree,
\[ a\quad\text{and}\quad b \]are internal vertices.
Every Nontrivial Finite Tree Has Leaves
Every finite tree with at least two vertices has at least two leaves.
Intuitively, if we follow a path as far as possible in either direction, its endpoints cannot have unused neighbors without allowing the path to continue.
Those endpoints are leaves.
What Is a Rooted Tree?
A rooted tree is a tree in which one vertex has been designated as the root.
Choosing a root does not change the underlying edges.
It changes how we interpret the relationships among vertices.
Rooting the Running Tree
Suppose we choose \(a\) as the root.
Then the tree can be viewed as branching away from \(a\):
\[ a \]connects downward to \(b\) and \(c\), while \(b\) connects downward to \(d\) and \(e\).
The Root Has No Parent
In a rooted tree, every non-root vertex has exactly one parent.
The root has no parent.
If \(a\) is the root in the running tree, then
\[ \boxed{\text{parent}(a)\text{ is undefined}}. \]Parents and Children
If vertex \(u\) is immediately closer to the root than adjacent vertex \(v\), then \(u\) is the parent of \(v\), and \(v\) is a child of \(u\).
With root \(a\),
\[ \text{children}(a)=\{b,c\} \]and
\[ \text{children}(b)=\{d,e\}. \]Siblings
Vertices with the same parent are called siblings.
Since \(d\) and \(e\) both have parent \(b\),
\[ \boxed{d\text{ and }e\text{ are siblings}}. \]Likewise, \(b\) and \(c\) are siblings because they share parent \(a\).
Ancestors
An ancestor of a vertex is a vertex that appears earlier on the unique path from the root to that vertex.
For \(d\), the root-to-\(d\) path is
\[ a,b,d. \]Therefore the ancestors of \(d\) are
\[ \boxed{a\text{ and }b}. \]Descendants
A vertex \(v\) is a descendant of \(u\) if \(u\) is an ancestor of \(v\).
In the rooted running tree, the descendants of \(a\) are
\[ b,c,d,e, \]while the descendants of \(b\) are
\[ d,e. \]Rooted Leaves
In a rooted tree, a leaf is often described as a vertex with no children.
In the running rooted tree,
\[ c,\qquad d,\qquad e \]have no children and are leaves.
Internal Vertices in a Rooted Tree
An internal vertex in a rooted tree is a vertex with at least one child.
With root \(a\), the internal vertices are
\[ \boxed{a\text{ and }b}. \]Depth of a Vertex
The depth of a vertex is the number of edges on the unique path from the root to that vertex.
The root has depth
\[ \boxed{0}. \]In the running rooted tree,
\[ \operatorname{depth}(b)=1,\qquad \operatorname{depth}(d)=2. \]Levels
Vertices with the same depth are often said to lie on the same level.
In the running rooted tree:
- level \(0\): \(a\);
- level \(1\): \(b,c\);
- level \(2\): \(d,e\).
Height of a Rooted Tree
The height of a rooted tree is the greatest depth of any vertex.
In the running rooted tree, the maximum depth is \(2\).
\[ \boxed{\operatorname{height}(T)=2}. \]Height of a Vertex
Some contexts also define the height of a vertex as the greatest number of edges on a downward path from that vertex to a leaf.
Under that convention,
\[ \operatorname{height}(b)=1 \]because \(b\) is one edge above the leaves \(d\) and \(e\).
Subtrees
A subtree rooted at \(v\) consists of \(v\) together with all of its descendants and the edges connecting them.
In the running rooted tree, the subtree rooted at \(b\) contains
\[ \{b,d,e\} \]with edges
\[ \{b,d\},\qquad\{b,e\}. \]Root Choice Changes Hierarchical Roles
The same unrooted tree can be rooted at different vertices.
If the root changes, parent-child, ancestor-descendant, depth, and height relationships may also change.
The underlying undirected tree remains the same.
Example: Re-Rooting the Tree
If \(b\) becomes the root instead of \(a\), then \(a\), \(d\), and \(e\) become children of \(b\).
Vertex \(c\) then becomes a child of \(a\).
The edges have not changed; only the hierarchy has.
Binary Trees
A binary tree is a rooted tree in which each vertex has at most two children.
Binary trees appear frequently in search structures, decision processes, coding, and recursive algorithms.
More specialized binary-tree types will be studied when needed.
Ordered Rooted Trees
In some rooted trees, the children of each vertex have a specified order.
Such a structure is called an ordered rooted tree.
For example, in a binary tree one child may be designated the left child and another the right child.
Unordered Rooted Trees
In an unordered rooted tree, the children of a vertex form a collection without a prescribed left-to-right order.
Exchanging the visual positions of siblings does not change the rooted-tree structure.
Trees as Hierarchies
Rooted trees naturally represent hierarchical relationships.
Examples include:
- organizational structures;
- file and folder systems;
- classification systems;
- decision trees;
- dependency structures;
- family-like ancestry models;
- recursive computations.
Trees as Minimal Connection Networks
A tree connects all of its vertices without redundant cycles.
This makes trees natural models for systems where connectivity is required but unnecessary links are undesirable.
The next lesson on spanning trees will apply this idea to larger connected graphs.
Equivalent Characterizations of a Tree
For a finite graph \(G\), the following conditions are equivalent:
- \(G\) is connected and acyclic;
- every pair of vertices is joined by exactly one path;
- \(G\) is connected and removing any edge disconnects it;
- \(G\) is acyclic and adding any missing edge creates a cycle;
- \(G\) is connected and has \(|V|-1\) edges;
- \(G\) is acyclic and has \(|V|-1\) edges.
These are different ways of recognizing the same structure.
Example: Recognizing a Tree by Edge Count
Suppose a graph has \(10\) vertices, \(9\) edges, and is connected.
Since
\[ |E|=|V|-1, \]and the graph is connected,
\[ \boxed{\text{the graph is a tree}}. \]Example: Recognizing a Non-Tree
Suppose a connected graph has \(10\) vertices and \(10\) edges.
A tree with \(10\) vertices would have only
\[ 9 \]edges.
Therefore the graph cannot be a tree. At least one cycle must be present.
Common Error: Thinking Every Acyclic Graph Is a Tree
A tree must be connected.
A disconnected acyclic graph is a forest, not a tree.
Common Error: Thinking Every Connected Graph Is a Tree
A connected graph may contain cycles.
The graph is a tree only when it is both connected and acyclic.
Common Error: Counting the Root as Its Own Parent
The root has no parent.
Parent relationships begin with vertices one level below the root.
Common Error: Confusing Degree with Number of Children
In a rooted tree, a non-root internal vertex has one edge to its parent in addition to its edges to children.
Therefore its graph-theoretic degree may be one greater than its number of children.
For example, if \(b\) has children \(d\) and \(e\) and parent \(a\), then
\[ \deg(b)=3 \]even though \(b\) has only two children.
Common Error: Assuming a Drawing Determines the Root
Drawing one vertex at the top does not automatically make it the root.
A root must be explicitly designated by the structure or the problem.
Common Error: Confusing Depth and Height
Depth measures downward from the root to a vertex.
Tree height measures the greatest depth in the tree.
Under the vertex-height convention, vertex height measures downward from that vertex to a deepest leaf.
A Reliable Procedure for Recognizing a Tree
- Check whether the graph is connected.
- Check whether it contains a cycle.
- If it is connected and acyclic, it is a tree.
- For finite graphs, use \(|E|=|V|-1\) as an additional consistency check.
- Remember that edge count alone is not sufficient without another structural condition.
A Reliable Procedure for Reading a Rooted Tree
- Identify the root.
- Trace the unique path from the root to each vertex.
- Identify each non-root vertex's parent.
- Identify the children of each internal vertex.
- Use repeated parent relationships to identify ancestors and descendants.
- Count root-to-vertex edges to determine depth.
- Find the maximum depth to determine tree height.
- Identify vertices with no children as rooted leaves.
Example: Full Rooted-Tree Workflow
Suppose a rooted tree has edges
\[ \{r,a\},\{r,b\},\{a,c\},\{a,d\},\{b,e\} \]with root \(r\).
Then
\[ \text{children}(r)=\{a,b\}, \] \[ \text{children}(a)=\{c,d\}, \]and
\[ \text{children}(b)=\{e\}. \]The leaves are
\[ c,d,e. \]Their depths are all \(2\), so
\[ \boxed{\operatorname{height}(T)=2}. \]Practice 1: Tree or Not?
A graph is connected and contains no cycles.
What type of graph is it?
Practice 2: Edge Count
How many edges must a tree with \(15\) vertices have?
Practice 3: Forest
A graph contains no cycles but has three connected components.
Is it a tree? What general type of graph is it?
Practice 4: Unique Path
In a tree, how many distinct paths can connect two fixed vertices \(u\) and \(v\)?
Practice 5: Leaves
In a nontrivial tree, what degree does a leaf have?
Practice 6: Parent and Children
In the rooted tree
\[ r-a,\qquad r-b,\qquad a-c,\qquad a-d, \]with root \(r\), identify the parent of \(c\) and the children of \(a\).
Practice 7: Depth
In the same rooted tree, what is the depth of \(c\)?
Practice 8: Height
Suppose the deepest leaves of a rooted tree are \(4\) edges from the root.
What is the height of the tree?
Practice 9: Subtree
Suppose \(a\) has descendants \(c,d,e\).
What vertices belong to the subtree rooted at \(a\)?
Practice 10: Identify the Error
A student says, “This graph has \(8\) vertices and \(7\) edges, so it must be a tree.”
Explain what additional information is needed.
Practice Answers
Practice 1
Connected and acyclic is exactly the definition of a tree:
\[ \boxed{\text{tree}}. \]Practice 2
A finite tree with \(n\) vertices has \(n-1\) edges:
\[ 15-1=14. \] \[ \boxed{14\text{ edges}}. \]Practice 3
Because the graph is disconnected, it is not a tree.
Since it contains no cycles, it is a forest:
\[ \boxed{\text{forest with three tree components}}. \]Practice 4
Every pair of vertices in a tree is joined by exactly one path:
\[ \boxed{1}. \]Practice 5
A leaf in a nontrivial unrooted tree has degree
\[ \boxed{1}. \]Practice 6
The parent of \(c\) is \(a\), and the children of \(a\) are \(c\) and \(d\):
\[ \boxed{\text{parent}(c)=a,\qquad \text{children}(a)=\{c,d\}}. \]Practice 7
The root-to-\(c\) path is
\[ r,a,c, \]which uses two edges. Therefore,
\[ \boxed{\operatorname{depth}(c)=2}. \]Practice 8
Tree height is the maximum depth:
\[ \boxed{4}. \]Practice 9
A subtree rooted at \(a\) contains \(a\) and all of its descendants:
\[ \boxed{\{a,c,d,e\}}. \]Practice 10
The edge count
\[ |E|=|V|-1 \]is necessary for a finite tree, but it does not by itself guarantee that the graph is a tree.
We also need to know, for example, that the graph is connected or that it is acyclic.
\[ \boxed{\text{edge count alone is insufficient}}. \]What to Remember
- A tree is a connected graph with no cycles.
- A forest is an acyclic graph whose components are trees.
- Every pair of vertices in a tree has exactly one path between them.
- Removing any edge from a tree disconnects it.
- Adding an edge to a tree creates a cycle.
- A finite tree with \(n\) vertices has \(n-1\) edges.
- A rooted tree designates one vertex as the root.
- Every non-root vertex has exactly one parent.
- Children, siblings, ancestors, descendants, depth, height, and subtrees depend on the chosen root.
- Leaves are terminal vertices; in a rooted tree they have no children.
Where We Go Next
A tree gives a connected, cycle-free structure. Larger connected graphs often contain many extra edges and cycles, but we can extract a tree that still reaches every vertex.
The next lesson, Spanning Trees, develops these full-vertex tree structures and explains how they capture minimal connectivity inside a connected graph.