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.
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.
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{.}\)
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 of TheoremĀ 16.3.1, 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.
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.
Consider the contrapositive of this logical implication, assuming that StatementĀ 3 is false and proving that StatementĀ 2 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.
Again, consider the contrapositive of this logical implication, assuming that StatementĀ 1 is false and proving that StatementĀ 3 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. This implies 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Ā 2, 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:
