Prove |E| = |V| - 1 by induction

Question

Any idea how to do this? I need to prove that let T = (V, E) be a tree, and then prove by induction that |E| = |V| - 1. Thankyou!

Answer 1

Ok, so base case: just a single vertex, no edges. So: $|E| = |V|-1$ since 0 =1-1

Inductive step: Suppose we have a tree with a top vertex, and two subtrees $T_1$ and $T_2$ below this top vertex. By inductive hypothesis, we can assume that for the two trees it holds that $|E_1| = |V_1| -1$ and $|E_2|=|V_2|-1$. Now, we have a total of $|V|=|V_1|+|V_2|+1$ vertices in the tree as a whole, and $|E|=|E_1|+|E_2| + 2$ edges. So: $|E|=|E_1|+|E_2|+2 = |V_1| -1+|V_2|-1+2= |V_1|+|V_2|+1-1=|V|-1$ as desired.

So, by structural induction, we have our desired result.

Ok so that is for binary trees. If nodes can have any number of children, you can generalize the proof to that as well, using the inductive hypothesis that $|E_i|=|V_i|-1$ for every subtree.