12.4: Trees

A special class of graphs that arise often in graph theory, is the class of trees. If a mathematician suspects that something is true for all graphs, one of the first families of graphs for which s/he will probably try to prove it, is the family of trees because their strong structure makes them much easier to work with than many other families of graphs.

Definition: Tree, Forest, and Leaf

• A tree is a connected graph that has no cycles.
• A forest is a disjoint union of trees. So a forest is a graph that has no cycles (but need not be connected).
• A leaf is a vertex of valency \(1\) (in any graph, not just in a tree or forest).

Notice that the graph \(P_n\) is a tree, for every \(n ≥ 1\). We prove some important results about the structure of trees.

Proposition \(\PageIndex{1}\)

Let \(T\) be a connected graph with no cycles. Then deleting any edge from \(T\) disconnects the graph.

Proof

If \(T\) has no edges, the statement is vacuously true. We may thus assume that \(T\) has at least one edge. Let \(\{u, v\}\) be an arbitrary edge of \(T\). (Since a loop is a cycle, we must have \(u \neq v\) even if we were not assuming that our graphs are simple.)

Towards a contradiction, suppose that deleting \(\{u, v\}\) from \(T\) does not disconnect \(T\). Then by the definition of a connected graph, there is a \(u − v\) walk in \(T \setminus \{u, v\}\). By Proposition 12.3.1, the shortest \(u − v\) walk in \(T \setminus \{u, v\}\) must be a \(u − v\) path. If we take this same walk in \(T\) and add u to the end, this will still be a walk in \(T\) since \(T\) contains the edge uv. Since the walk in \(T \setminus \{u, v\}\) was a path, no vertices were repeated. Adding \(u\) to the end of this walk makes a walk (certainly of length at least \(2\)) in which no vertex is repeated except that the first and last vertices are the same: by definition, a cycle. Thus, \(T\) has a cycle, contradicting our hypothesis. This contradiction serves to prove that deleting any edge from \(T\) disconnects the graph.

Since a tree is a connected graph with no cycles, this shows that deleting any edge from a tree will disconnect the graph.

Proposition \(\PageIndex{2}\)

Every tree that has at least one edge, has at least two leaves.

Proof

We prove this by strong induction on the number of vertices. Notice that a (simple) graph on one vertex must be \(K_1\), which has no edges, so the proposition does not apply. Therefore our base case will be when there are \(2\) vertices.

Base case: \(n = 2\). Of the two (unlabeled) graphs on \(2\) vertices, only one is connected: \(K_2\) (or \(P_1\); these are isomorphic). Both of the vertices have valency \(1\), so there are two leaves. This completes the proof of the base case.

Induction step: We begin with the strong inductive hypothesis. Let \(k ≥ 2\) be arbitrary. Suppose that for every \(2 ≤ i ≤ k\), every tree with \(i\) vertices has at least two leaves. (Since \(i ≥ 2\) and a tree is a connected graph, every tree on \(i\) vertices has at least one edge, so we may omit this part of the hypothesis.)

Let \(T\) be a tree with \(k + 1\) vertices. Since \(k + 1 > 1\), \(T\) has at least one edge. Choose any edge \(\{u, v\}\) of \(T\), and delete it. By Proposition 12.4.1, the resulting graph is disconnected. By Proposition 12.3.2, it cannot have more than two connected components, so it must have exactly two connected components. Furthermore, by the proof of that proposition, the components are \(T_u\) (the connected component that contains the vertex \(u\)) and \(T_v\) (the connected component that contains the vertex \(v\)).

Since \(T\) has no cycles, neither do \(T_u\) or \(T_v\). Since they are connected components, they are certainly connected. Therefore, both \(T_u\) and \(T_v\) are trees. Since \(u\) is not a vertex of \(T_v\) and \(v\) is not a vertex of \(T_u\), each of these trees has at most \(k\) vertices.

If both \(T_u\) and \(T_v\) have at least two vertices, then we can apply our induction hypothesis to both. This tells us that \(T_u\) and \(T_v\) each have at least two leaves. In particular, \(T_u\) must have some leaf \(x\) that is not \(u\), and \(T_v\) must have some leaf \(y\) that is not \(v\). Deleting \(u_v\) from \(T\) did not change the valency of either \(x\) or \(y\), so \(x\) and \(y\) must also have valency \(1\) in \(T\). Therefore \(T\) has at least two leaves. This completes the induction step and therefore the proof, in the case where \(T_u\) and \(T_v\) each have at least two vertices. We must still consider the possibility that at least one of \(T_u\) and \(T_v\) has only one vertex.

Since \(k + 1 ≥ 3\), at least one of \(T_u\) and \(T_v\) must have two vertices, so only one of them can have only one vertex. Without loss of generality (since nothing in our argument so far made any distinction between \(u\) and \(v\), we can switch \(u\) and \(v\) if we need to), we may assume that \(T_v\) has only one vertex, and \(T_u\) has at least two vertices. Applying our induction hypothesis to \(T_u\), we conclude that \(T_u\) has some leaf \(x\) that is not \(u\), and that is also a leaf of \(T\). Furthermore, since \(T_v\) has only one vertex, this means that deleting the edge \(uv\) left \(v\) as an isolated vertex, so \(u_v\) was the only edge incident with \(v\) in \(T\). Therefore, \(v\) is a leaf of \(T\). Thus, \(T\) has at least two leaves: \(x\) and \(v\). This completes the induction step and therefore the proof, in the case where at least one of \(T_u\) and \(T_v\) has only one vertex. Since we have dealt with all possibilities, this completes our induction step.

By the Principle of Mathematical Induction, every tree that has at least one edge, has at least two leaves.

The next result will be left to you to prove.

Proposition \(\PageIndex{3}\)

If a leaf is deleted from a tree, the resulting graph is a tree.

Theorem \(\PageIndex{1}\)

The following are equivalent for a graph \(T\) with \(n\) vertices:

1. \(T\) is a tree;
2. \(T\) is connected and has \(n − 1\) edges;
3. \(T\) has no cycles, and has \(n − 1\) edges;
4. \(T\) is connected, but deleting any edge leaves a disconnected graph.

Proof

We will prove that the statements are equivalent by showing that \(1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 1\). Thus, by using a sequence of implications, we see that any one of the statements implies any other.

\((1 ⇒ 2)\) We assume that \(T\) is a tree, and we would like to deduce that \(T\) is connected and has \(n−1\) edges. By the definition of a tree, \(T\) is connected. We will use induction on \(n\) to show that \(T\) has \(n − 1\) edges.

Base case: \(n = 1\). There is only one (unlabeled) graph on one vertex, it is \(K_1\), so \(T \cong K_1\), which has no edges. Since \(0 = n − 1\), this completes the proof of the base case.

Inductive step: We begin with the inductive hypothesis. Let \(k ≥ 1\) be arbitrary, and suppose that every tree on \(k\) vertices has \(k − 1\) edges.

Let \(T\) be an arbitrary tree with \(k + 1\) vertices. Since \(k + 1 ≥ 2\) and \(T\) is connected, \(T\) must have at least one edge, so by Proposition 12.4.2, \(T\) has at least two leaves. Let \(v\) be a leaf of \(T\). By Proposition 12.4.3, \(T \setminus \{v\}\) is a tree. Also, \(T \setminus \{v\}\) has \(k\) vertices, so we can apply our induction hypothesis to conclude that \(T \setminus \{v\}\) has \(k − 1\) edges. Since \(v\) was a leaf, \(T\) has precisely one more edge than \(T \setminus \{v\}\), so \(T\) must have \(k = (k + 1) − 1\) edges. This completes our inductive step.

By the Principle of Mathematical Induction, every tree on \(n\) vertices has \(n − 1\) edges.

\((2 ⇒ 3)\) We assume that \(T\) is connected and has \(n − 1\) edges. We need to deduce that \(T\) has no cycles.

Towards a contradiction, suppose that \(T\) has a cycle. Repeatedly delete edges that are in cycles until no cycles remain. By Proposition 12.3.3 (used repeatedly), the resulting graph is connected, so by definition it is a tree. Since we have already proven that \(1 ⇒ 2\), this tree must have \(n − 1\) edges. Since we started with \(n − 1\) edges and deleted at least one (based on our assumption that \(T\) has at least one cycle), this is a contradiction. This contradiction serves to prove that \(T\) must not have any cycles.

\((3 ⇒ 4)\) We assume that \(T\) has no cycles, and has \(n − 1\) edges. We must show that \(T\) is connected, and that deleting any edge leaves a disconnected graph. We begin by showing that \(T\) is connected; we prove this by induction on \(n\).

Base case: \(n = 1\). Then \(T \cong K_1\) is connected.

Inductive step: We begin with the inductive hypothesis. Let \(k ≥ 1\) be arbitrary, and suppose that every graph on \(k\) vertices that has \(k − 1\) edges and no cycles, is connected.

Let \(T\) be an arbitrary graph with \(k + 1\) vertices that has \(k\) edges and no cycles. By Euler’s handshaking lemma,

\[\sum_{v∈V} d(v) = 2k. \]

If each of the \(k + 1\) vertices had valency \(2\) or more, then we would have

\[\sum_{v∈V} d(v) ≥ 2(k + 1) \]

(this is a lot like the Pigeonhole Principle in concept, but the Pigeonhole Principle itself doesn’t apply to this situation). Since \(2k < 2(k + 1)\), there must be some vertex \(v\) that does not have valency \(2\) or more. Delete \(v\). In so doing, we delete at most \(1\) edge, since \(v\) has at most \(1\) incident edge. Thus, the resulting graph has \(k\) vertices and \(k\) or \(k − 1\) edges, and since \(T\) has no cycles, neither does \(T \setminus \{v\}\).

If \(T \setminus \{v\}\) has \(k\) edges, then deleting any of the edges results in a graph on \(k\) vertices with no cycles and \(k−1\) edges, which by our inductive hypothesis must be connected. Therefore \(T \setminus \{v\}\) is a connected graph that remains connected after any edge is deleted. By Proposition 12.4.1 (in the contrapositive), this means that \(T \setminus \{v\}\) must contain a cycle, but this is a contradiction. This contradiction serves to prove that \(T \setminus \{v\}\) cannot have \(k\) edges.

Thus, \(T \setminus \{v\}\) has \(k − 1\) edges and \(k\) vertices, and no cycles. By our inductive hypothesis, \(T \setminus \{v\}\) must be connected. Furthermore, the fact that \(T \setminus \{v\}\) has \(k − 1\) edges means that \(v\) is incident to an edge, which must have its other endvertex in \(T \setminus \{v\}\). Therefore \(T\) is connected. This completes the inductive step.

By the Principle of Mathematical Induction, every graph on \(n\) vertices with no cycles and \(n − 1\) edges is connected.

It remains to be shown that deleting any edge leaves a disconnected graph, but now that we know that \(T\) is connected, this follows from Proposition 12.4.1.

\((4 ⇒ 1)\) We assume that \(T\) is connected, but deleting any edge leaves a disconnected graph. By the definition of a tree, we must show that \(T\) has no cycles. This follows immediately from Proposition 12.3.3.

Exercise \(\PageIndex{1}\)

1. Prove Proposition 12.4.3.
2. Draw a tree on \(6\) vertices.
3. There are two non-isomorphic trees on \(4\) vertices. Find them.
4. There are \(11\) non-isomorphic graphs on \(4\) vertices. Draw all \(11\), and under each one indicate: is it connected? Is it a forest? Is it a tree?

[Hint: One has \(0\) edges, one has \(1\) edge, two have \(2\) edges, three have \(3\) edges, two have \(4\) edges, one has \(5\) edges, and one has \(6\) edges.