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.
Loops exist in \(G\text{.}\)
Some pair of distinct vertices in \(G\) is not connected.
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.
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.
Graph \(G\) is not connected.
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.
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.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.
Assume that \(G\) is a tree. Then it is connected. To prove that the number of edges is \(\card{E} = 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{,}\)\(\card{E} = 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.5). 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.
Figure16.3.2.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 \(\card{E} = (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 \(\card{E} = 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.11\(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,\dotsc,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.5). 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:
