Chapter 10 Trees
Exercises Practice Problems
1. Trees on 4 Vertices.
Draw all non-isomorphic trees on 4 vertices Solution.
2. Trees on 5 Vertices.
Draw all non-isomorphic trees on 5 vertices Solution.
3. Leaves on Trees.
More generally, consider the set of trees on \(n \geq 3\) vertices. Which tree has the fewest leaves? Which tree has the most leaves? Draw these trees and state how many leaves each has. Solution.
4. A Tree Has At Least 2 Leaves.
In this problem, you will give another proof that a tree on \(n \geq 3\) has at least two leaves (recall that a leaf is a vertex with degree equal 1). Let \(G\) be a tree on \(n\geq 3\) vertices. Let \(S\) be the set of all paths from one vertex to another on \(G\text{.}\) Among all the paths in \(S\text{,}\) let \(P\) be a path with the most edges.
How does this path \(P\) help us to find two leaves? Solution.
Let \(P = (v_1, v_2, \ldots, v_k)\) be a path of maximum length. We claim that the endpoints \(v_1, v_k\) of \(P\) are leaves. AFSOC that \(v_1\) is not a leaf. Then \(v_1\) has another neighbor \(u\) besides \(v_2\text{.}\) Since \(G\) is a tree, this neighbor is not already on the path \(P\) because this new edge would create a cycle. But then we can find a longer path by adding the edge from \(v_1\) to \(u\text{,}\) a contradiction. The same argument applies to \(v_k\text{.}\) Therefore \(v_1, v_k\) are both leaves in \(G\text{.}\)
5. Definitions for a Tree.
Here is a theorem that gives four different ways to describe a tree.
Theorem: The following statements are equivalent for a graph \(G=(V,E)\) on \(n\) vertices
\(G\) is connected and acyclic
\(G\) is connected and \(|E|=n-1\)
\(G\) is acyclic and \(|E|=n-1\)
There is a unique path between each pair of vertices in \(G\)
\(G\) is connected but deleting any edge disconnects the graph.
We will focus on (d) \(\Rightarrow\) (a) and the equivalence (a) \(\Leftrightarrow\) (e).
Prove that (d) \(\Rightarrow\) (a) using a proof by contradiction. Assuming that (d) holds, why must \(G\) be connected? Why must \(G\) be acyclic? Solution.
Assume that there is a unique path between each pair of vertices in \(G\text{.}\)
The graph is connected: a path between \(u\) and \(v\) is a walk between \(u\) and \(v\text{.}\) So each pair of vertices is joined by a walk.
AFSOC that there is a cycle \(C\) in the graph. Let \(e=(u,v)\) be an edge in \(C\text{.}\) Then there are two paths between these vertices: the edge \(e\) and \(C-e\text{,}\) the cycle minus this edge. This contradicts the fact that there is a unique path between \(u\) and \(v\text{.}\)
Prove that (a) \(\Rightarrow\) (e) using a proof by contradiction. Assume that (a) holds, but there is an edge \(e\) such that the graph \(G-e\) obtained by removing \(e\) is connected. Why does this lead to a contradiction? Solution.
Let \(G\) be connected and acyclic. AFSOC that there is an edge \(e=(u,v)\) such that the graph \(G-e\) obtained by removing \(e\) is connected. This means that there is a \((u,v)\)-path \(P\) in \(G-e\text{.}\) But then \(P+e\) is a cycle in \(G\text{,}\) a contradiction.
Prove that (e) \(\Rightarrow\) (a) by proving the contrapositive statement "not (a) \(\Rightarrow\) not (e)." Solution.
Let \(G\) be a connected graph. We prove that if \(G\) contains a cycle then there exists an edge \(e\) such that \(G-e\) is connected. Pick a cycle \(C\) in the graph and let \(e=(u,v)\) be an edge in \(C\text{.}\) Then \(P=C-e\) is a path in \(G-e\text{.}\) We now show that \(G-e\) is connected. Intuitively, any \((x,y)\)-path that uses \(e\) can be "re-rerouted" to use the other part of the cycle instead. Let \(x,y\) be any two vertices. Since \(G\) is connected, there is a walk \(Q\) from \(x\) to \(y\text{.}\) If \(e \notin Q\) then \(Q\) is a walk in \(G-e\text{.}\) If \(e \in Q\text{,}\) then we can split \(Q\) into \(Q_1 \cup e \cup Q_2\) where \(Q_1\) and \(Q_2\) are walks. But then \(Q_1 + P + Q_2\) is an \((x,y)\)-walk in \(G-e\text{.}\) Therefore, \(G-e\) is connected.