Definition 10.3.1.
A graph is circuit-free if it has no nontrivial circuits.
Section 10.3 Trees
In this section we look at a special type of graph called a tree. Trees are useful in many applications, such as probability trees or decision trees.
Definition 10.3.2.
A graph is a tree if it is connected and circuit-free.
The trivial tree is just a single vertex. While the empty tree has no vertices (and, hence, no edges).
Definition 10.3.3.
A graph is a forest if it is circuit-free. We can think of a forest as a collection of trees.
Example 10.3.4. Trees and Not Trees.
Definition 10.3.7.
A terminal vertex or leaf is a vertex of degree 1. Vertices of degree greater than 1 are internal or branch vertices.
We now define some special types of trees, and related terms.
A rooted tree has one vertex, \(r\text{,}\) designated as the root.
- The level of a vertex, \(v\text{,}\) is the number of edges from \(v\) to the root, \(r\text{.}\)
- The height of a tree is the maximum level of the tree.
- Let \(v\) be a vertex in a rooted tree. Then the children of \(v\) are the vertices adjacent to \(v\text{,}\) one level below \(v\) (think of the root at the top of the tree, with each successive level below the previous one).
- The parent of a vertex \(v\) is the adjacent vertex one level up from \(v\text{.}\)
- The siblings of a vertex \(v\) are the vertices with the same parent as \(v\text{.}\)
- The ancestors of a vertex \(v\) are the vertices on the path from \(v\) to \(r\text{,}\) not including \(v\text{.}\)
- The descendants of a vertex \(v\) are the vertices on the subtree taking \(v\) as the root, not including \(v\text{.}\)
Example 10.3.8. Rooted Tree.
In the example, let \(r\) be the root of the tree.
Then \(v\) is at level 2, \(d\) is at level 4, and \(r\) is at level 0.
The height of the tree is 4.
The children of \(v\) are \(c_1\) and \(c_2\text{.}\)
The only sibling of \(v\) is \(s\text{;}\) the parent of \(v\) is \(p\text{.}\)
The ancestors of \(v\) are \(p\) and \(r\text{.}\) The descendants of \(v\) are \(c_1, c_2, d\text{.}\)
A binary tree is a rooted tree in which each vertex has at most two children.
A full binary tree is a rooted tree in which each branch vertex has exactly two children and all leaves are at the same height.
Example 10.3.10. Full Binary Tree.
Activity 10.3.1.
Draw the full binary tree of height 4. How many leaves does it have?
Activity 10.3.2.
In this activity we will explore the relationship between the number of edges and the number of vertices in a tree.
(a)
Draw a forest with 10 vertices that is not a tree.
(b)
Draw three different trees, each with 10 vertices.
(c)
How many edges does each graph in (b) have? Check with other students in the class. How many edges do their graphs have?
(d)
Draw a tree with 5 vertices and one with 12 vertices. How many edges do they have?
(e)
Can you draw a tree with 5 vertices with 7 edges? What about 5 edges? What is the most number of edges you can have? What is the fewest?
(f)
Form a conjecture about how many edges a tree with 10 vertices has. What about a tree with 5 vertices?
After experimenting you should be able to conjecture that a tree with 10 vertices has 9 edges, and a tree with 5 vertices must have 4 edges. This relationship is true in general.
Theorem 10.3.12.
For any positive integer, \(n\text{,}\) any tree with \(n\) vertices has \(n-1\) edges.
Activity 10.3.3.
In this activity we explore graphs with \(n\) vertices and \(n-1\) edges more generally.
(a)
Draw a graph with 7 vertices and 6 edges that is not a tree.
(b)
Draw a connected graph with 7 vertices and 6 edges that is not a tree.
(c)
Do you think either of the tasks in (a) or (b) is impossible?
(d)
Form a conjecture about graphs with \(n\) vertices and \(n-1\) edges.
We should be able to see that it is not possible to draw a connected graph with 7 vertices and 6 edges that is not a tree. This leads to the next theorem.
Theorem 10.3.13.
For any positive integer \(n\text{,}\) if a graph, \(G\text{,}\) is connected with \(n\) vertices and \(n-1\) edges, then \(G\) is a tree.
Reading Questions Check Your Understanding
1.
- \(n=1\)
- \(n=2\)
- \(n=3\)
- \(n=4\)
- No values of \(n\)
- All values of \(n\geq 1\text{.}\)
For which values of \(n\) is the complete graph \(K_n\) a tree?
2.
True.
False.
True or false: In a rooted tree, a vertex can have more than one parent.
3.
True.
- The root has 0 parents.
False.
- The root has 0 parents.
True or false: In a rooted tree, a vertex can have 0 parents.
4.
In the rooted tree in Figure 10.3.9, how many children does \(r\) have?
5.
In the rooted tree in Figure 10.3.9, how many descendants does \(p\) have?
6.
In the rooted tree in Figure 10.3.9, what is the level of \(p\text{?}\)
7.
How many leaves does the full binary tree of height 4 have?
8.
True.
False.
True or false: There exists a tree with 7 vertices and 9 edges.
9.
True.
False.
True or false: There exists a tree with 7 vertices and 5 edges.
10.
True.
False.
True or false: There exists a forest with 7 vertices and 5 edges.
11.
True.
False.
True or false: If a graph has 8 vertices and 7 edges it must be a tree.
12.
True.
False.
True or false: If a connected graph has 8 vertices and 7 edges it must be a tree.
13.
True.
False.
True or false: There exists a tree with 8 vertices and 2 leaves.
14.
True.
False.
True or false: There exists a tree with 8 vertices and 7 leaves.
Exercises Exercises
1.
What is the total degree of a tree with \(n\) vertices? Why?
2.
Consider the following lemma.
Lemma 10.3.14.
Any tree with more than one vertex has at least one vertex of degree 1.
This is a useful lemma for proving statements about trees. However, if the tree has infinitely many vertices and edges, then the lemma is false. Give an example of an infinite tree that has no vertex of degree 1.
3.
For each of the following, either draw a graph with the given properties or explain why no such graph exists.
- Tree, nine vertices, nine edges.
- Graph, connected, nine vertices, nine edges.
- Tree, five vertices, total degree 8
- Graph, six vertices, five edges, not a tree.
- Graph, connected, ten vertices, nine edges, has a circuit.
4.
Suppose a connected graph has twelve vertices and 11 edges. Must this graph have a vertex of degree 1? Explain your answer.
You have attempted of activities on this page.
