In this section, we’ll seek to answer the questions:
What is a tree? A forest?
What is a spanning tree, and when can we produce a spanning tree?
Activity6.1.1.
Consider the graphs below.
Figure6.1.2.Some small graphs.
For each of these graphs, find a subgraph with the smallest number of edges that is still connected and contains all the vertices.
For each of these graphs, find a subgraph with the largest number of edges that does not contain any cycles.
What do you notice about your answers to these questions? What do you wonder?
In this section, we explore certain special classes of graphs. We begin with trees; it may be helpful to review Definition 5.3.10.
Definition6.1.3.
A tree is a connected graph which contains no cycles. A forest is a graph which contains no cycles.
We sometimes also use the word acyclic to describe trees and forests. Trees are useful structures for modeling decisions, as well as searches. We will return to this notion later. For now, we establish an alternative characterization of trees.
Theorem6.1.4.
Suppose \(T\) is a graph such that between any pair of distinct vertices \(u,v\) there is a unique path. Then \(T\) is a tree.
Hint.
First, explain why \(T\) is connected. Then assume there is a cycle and reach a contradiction.
Theorem6.1.5.
Suppose \(T\) is a tree. Then there is a unique path between any two vertices of \(T\text{.}\)
Hint.
First, show there is at least one path between any two vertices of \(T\text{.}\) Then assume that there is a pair of vertices between which there are two paths, and build a cycle to reach a contradiction.
We can use Theorem 6.1.4 and Theorem 6.1.5 to give an alternative definition of a tree: a tree is a connected graph such that there is a unique path between any two of its vertices. We can also make the following observation about forests.
Corollary6.1.6.
A graph \(F\) is a forest if and only if between any pair of vertices in \(F\) there is at most one path.
We now return to Activity 6.1.1 to consider a feature of the minimal graphs you produced.
A vertex of degree 1 is called a leaf (yes, really). How many leaves does each of your minimal graphs have? Do you think this will always happen? State and prove a conjecture.
A common technique for proving statements about trees is sometimes known as leaf pruning, and goes hand-in-hand with induction on the number of vertices. At the inductive step, we assume that we have a tree with \(n+1\) vertices, temporarily prune one to apply our inductive hypothesis, and then put our \((n+1)\)st vertex back to reach our conclusion. Try to use this technique to prove the following.
Theorem6.1.8.
Let \(T\) be a tree with \(v\) vertices and \(e\) edges. Then \(e = v - 1\text{.}\)
