16.3: Identifying Trees

Theorem $\PageIndex{1}$: Characterizations of trees.

The following are equivalent for a graph $G = (V,E)$ with $\vert V \vert = n$ vertices.

1. Graph $G$ is a tree.
2. Graph $G$ is acyclic but the addition of any new edge would create a cycle.
3. Graph $G$ contains no loops and contains exactly one path between each pair of distinct vertices.
4. Graph $G$ is connected but every edge of $G$ is a bridge.
5. Graph $G$ is connected and has exactly $\vert E \vert = n-1$ edges.
6. Graph $G$ is acyclic and has exactly $\vert E \vert = n-1$ edges.

Proof of the equivalence of Statements 1–4.

Statement 1 implies Statement 2.

Suppose $G$ is a tree. By definition, it is acyclic. Furthermore, suppose we add an edge between vertices $v,v'\text{.}$ Since trees are connected, there was already a path from $v$ to $v'$ in $G\text{.}$ Traversing the new edge from $v'$ back to $v$ closes that path to a cycle.

Statement 2 implies Statement 3.

Considering the contrapositive, we will assume that Statement 3 is false, and prove that this implies that Statement 2 must also be false.

For Statement 3 to be false, one of the following must be true.

1. Loops exist in $G\text{.}$
2. Some pair of distinct vertices in $G$ is not connected.
3. Some pair of distinct vertices in $G$ is connected by more than one path.

In the first case, $G$ would not be acyclic, as a loop is the most basic form of cycle. In the second case, adding an edge between these two vertices that were previously unconnected by a path would not create a cycle, as the rest of that cycle other than the new edge would have been a path between the two vertices. And in the third case, if a pair of vertices is connected by more than one path then the parts of two such paths that are different could be concatenated (one forward, one reversed) to create a cycle, so that $G$ must be not be acyclic.

Thus, in all cases that make Statement 3 false, Statement 2 is also false.

Statement 3 implies Statement 4.

Again, we will consider the contrapositive, assuming that Statement 4 is false and proving that Statement 3 is also false.

For Statement 4 to be false, one of the following is true.

1. Graph $G$ is not connected.
2. Some edge in $G$ is not a bridge.

In the first case, $G$ must contain at least one pair of vertices that is not connected by any path. For the second case, suppose edge $e$ in $G$ is a loop. If $e$ is a loop, then $G$ contains loops. If $e$ is not a loop, then it is an edge between a pair of distinct vertices, say $v$ and $v'\text{.}$ But then removing $e$ from $G$ would leave a subgraph $G'$ that still contains both $v$ and $v'\text{,}$ and which is still connected. So this subgraph (and hence $G$) must contain a path between $v$ and $v'$ that does not involve $e\text{.}$ On the other hand, $v, e, v'$ is also a path between $v$ and $v'\text{.}$ So $v,v'$ is a pair of distinct vertices in $G$ for which there is more than one path between them.

Thus, in all cases that make Statement 4 false, Statement 3 is also false.

Statement 4 implies Statement 1.

Again, we consider the contrapositive of this logical implication, assuming that Statement 1 is false and proving that Statement 4 is also false. However, since both statements contain the substatement that $G$ is connected, we will not negate that part.

So assume that $G$ is connected but contains a proper cycle. We aim to prove that at least one edge in $G$ is not a bridge. In Activity 16.7.4, you are asked to prove that none of the edges in the proper cycle that $G$ contains is a bridge, which will complete the proof.

Proof of the equivalence of Statement 1, Statement 5, and Statement 6.

Statement 1 implies Statement 5.
Assume that $G$ is a tree. Then it is connected. To prove that the number of edges is $\vert E \vert = n - 1\text{,}$ we proceed by (strong) induction on $n\text{,}$ the number of vertices in $G\text{.}$

For the base base case of $n = 1\text{,}$ $\vert E \vert = 0$ is the only possibility, as loops are not allowed in a tree.

Now the induction step. Assume that every tree with $k \lt n$ vertices has $k - 1$ edges. Choose some edge in $G\text{.}$ By Statement 4, removing that edge creates two connected components, $G_1$ and $G_2\text{.}$ As $G$ is acyclic, these connected components are both trees (Statement 2 of Proposition 16.2.1). Let $k_1, k_2$ represent the number of vertices in $G_1,G_2\text{,}$ respectively, so that $k_1 + k_2 = n\text{.}$ Since each of $k_1$ and $k_2$ must be strictly less than $n\text{,}$ we may apply our indution hypothesis to each of $G_1$ and $G_2\text{,}$ so that $G_1$ has exactly $k_1 - 1$ edges and $G_2$ has exactly $k_2 - 1$ edges.

Figure $\PageIndex{1}$: Tree $G$ splits into subtrees $G_1,G_2$ after removal of an edge.

Adding up the number of edges in $G_1$ and $G_2\text{,}$ along with the single edge in $G$ that was removed to create these two connected components, we obtain $\vert E \vert = (k_1 - 1) + (k_2 - 1) + 1 = (k_1 + k_2) - 1 = n - 1,$ as desired.

Statement 5 implies Statement 6.
Consider the contrapositive of this logical implication, assuming that Statement 6 is false and proving that Statement 5 is also false. However, since both statements contain the substatement that $\vert E \vert = n - 1\text{,}$ we will not negate that part.

So assume that $G$ has $n - 1$ edges, but contains a proper cycle. We must prove that $G$ cannot be connected in this case. Choose an edge $e$ in the proper cycle and create a subgraph $G'$ by removing $e\text{.}$ Subgraph $G'$ now has $n$ vertices but $n - 2$ edges, and so by the contrapositive of Theorem 15.3.1 $G'$ cannot be connected. That means that $G'$ contains a pair of vertices $v_1,v_2$ between which no walk exists. If there is a walk between $v_1,v_2$ in $G$ but not in $G'\text{,}$ then that walk must involve the chosen $e\text{.}$ But then there would be another walk between $v_1,v_2$ in $G$ avoiding $e$ via the rest of the proper cycle containing $e\text{.}$ And this other walk would be in $G'$ since it does not involve $e\text{.}$ Except that we assumed there was no walk between $v,v'$ in $G'\text{,}$ hence there also can be no walk between them in $G\text{.}$ Thus, $G$ is not connected.

Statement 6 implies Statement 1.
Again, consider the contrapositive of this logical implication, assuming that Statement 1 is false and proving that Statement 6 is also false. However, since both statements contain the substatement that $G$ is acyclic (part of the definition of tree), we will not negate that part.

So assume that $G$ is acyclic but not a tree, i.e. that $G$ is not connected. We must prove that the number of edges in $G$ is different from $n - 1\text{,}$ where $n$ is the number of vertices in $G\text{.}$ Let $G_1,G_2,\ldots,G_\ell$ be the connected components of $G\text{.}$ Now, since $G$ is assumed acyclic, each of these connected components is a tree (Statement 2 of Proposition 16.2.1). We have already proved above that Statement 1 implies Statement 5, so if we write $k_i$ for the number of vertices in component $G_i\text{,}$ then we may conclude that the number of edges in component $G_i$ is $k_i - 1\text{.}$ As the components make up the entire graph $G\text{,}$ we may add up the vertices and edges in each component to get the totals in the full graph:

$$\begin{equation*} n = k_1 + k_2 + \cdots + k_\ell, \end{equation*}$$
$$\begin{align*} \vert E \vert & = (k_1 - 1) + (k_2 - 1) + \cdots + (k_\ell - 1) \\ & = (k_1 + k_2 + \cdots + k_\ell) - \ell \\ & = n - \ell \text{.} \end{align*}$$
Since we assume $G$ is not connected, we have $\ell \ge 2\text{,}$ and so $\vert E \vert \neq n - 1$ as desired.