I am currently trying to prove that for any tree, e=v-1, where e is the number of edges and v is the number of vertices. My first thought was to perform induction on the structure of the tree. Clearly, this proposition is true for n=1 case. I had the thought to assume it was true for the nth case and prove it for the (n+1)th case. However, there are many different ways of adding one vertex to a single graph. I could add it as a leaf, in which case the proposition would be true, or I could add it as an interior node, in which case I would need to “unconnect” two nodes, attach the new vertex to one of them and the edge to the other. The new vertex can only have one edge because if it had multiple, then the added edge would form a cycle. To me, this proof seemed alright. However, this is what my textbook wrote on the topic:
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 ≥ 1 . 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 ≥ 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 ? Well, it has one more edge than , T ′ , so it has k edges. But this is exactly what we wanted: v=k+1, e=k so indeed . e = v − 1 . This completes the inductive case, and the proof.
There is a very important feature of this induction proof that is worth noting. Induction makes sense for proofs about graphs because we can think of graphs as growing into larger graphs. However, this does NOT work. It would not be correct to start with a tree with k vertices, and then add a new vertex and edge to get a tree with k+1 vertices, and note that the number of edges also grew by one. Why is this bad? Because how do you know that every tree with k+1 vertices is the result of adding a vertex to your arbitrary starting tree? You don't!
The point is that whenever you give an induction proof that a statement about graphs that holds for all graphs with v vertices, you must start with an arbitrary graph with v+1 vertices, then reduce that graph to a graph with v vertices, to which you can apply your inductive hypothesis.
I didn’t quite understand why reverse induction is valid in this case. I understand the general proof structure for classic/forward induction (namely that if a statement is true for a base case, and assuming the inductive principle holds, then by proof by contradiction there must be a smallest case for which it is false, which leads to RAA). I did not think of a similar proof for reverse induction in this case.