Discrete Mathematics: An Active Approach to Mathematical Reasoning

Section10.3Trees

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.

Definition10.3.1.

A graph is circuit-free if it has no nontrivial circuits.

Definition10.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).

Definition10.3.3.

A graph is a forest if it is circuit-free. We can think of a forest as a collection of trees.

Definition10.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{.}$$
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.

Activity10.3.1.

Draw the full binary tree of height 4. How many leaves does it have?

Activity10.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.

Activity10.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.

1.

For which values of $$n$$ is the complete graph $$K_n$$ a tree?
• $$n=1$$
• $$n=2$$
• $$n=3$$
• $$n=4$$
• No values of $$n$$
• All values of $$n\geq 1\text{.}$$

2.

True or false: In a rooted tree, a vertex can have more than one parent.
• True.

• False.

3.

True or false: In a rooted tree, a vertex can have 0 parents.
• True.

• The root has 0 parents.
• False.

• The root has 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 or false: There exists a tree with 7 vertices and 9 edges.
• True.

• False.

9.

True or false: There exists a tree with 7 vertices and 5 edges.
• True.

• False.

10.

True or false: There exists a forest with 7 vertices and 5 edges.
• True.

• False.

11.

True or false: If a graph has 8 vertices and 7 edges it must be a tree.
• True.

• False.

12.

True or false: If a connected graph has 8 vertices and 7 edges it must be a tree.
• True.

• False.

13.

True or false: There exists a tree with 8 vertices and 2 leaves.
• True.

• False.

14.

True or false: There exists a tree with 8 vertices and 7 leaves.
• True.

• False.

ExercisesExercises

1.

What is the total degree of a tree with $$n$$ vertices? Why?

2.

Consider the following lemma.
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.
1. Tree, nine vertices, nine edges.
2. Graph, connected, nine vertices, nine edges.
3. Tree, five vertices, total degree 8
4. Graph, six vertices, five edges, not a tree.
5. 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.