Proof

We will give a proof by induction on the number of vertices in the tree. That is, we will prove that every tree with \(v\) vertices has exactly \(v-1\) edges, and then use induction to show this is true for all \(v \ge 1\text{.}\)

For the base case, consider all trees with \(v = 1\) vertices. There is only one such tree: the graph with a single isolated vertex. This graph has \(e = 0\) edges, so we see that \(e = v-1\) as needed.

Now for the inductive case, fix \(k \ge 1\) and assume that all trees with \(v=k\) vertices have exactly \(e=k-1\) edges. Now consider an arbitrary tree \(T\) with \(v = k+1\) vertices. By Proposition 4.2.3, \(T\) has a vertex \(v_0\) of degree one. Let \(T'\) be the tree resulting from removing \(v_0\) from \(T\) (together with its incident edge). Since we removed a leaf, \(T'\) is still a tree (the unique paths between pairs of vertices in \(T'\) are the same as the unique paths between them in \(T\)).

Now \(T'\) has \(k\) vertices, so by the inductive hypothesis, has \(k-1\) edges. What can we say about \(T\text{?}\) Well, it has one more edge than \(T'\text{,}\) so it has \(k\) edges. But this is exactly what we wanted: \(v=k+1\text{,}\) \(e=k\) so indeed \(e = v-1\text{.}\) This completes the inductive case, and the proof.