I just learned it in class that when using induction to prove a tree problem, we should always remove a vertex instead of adding one in induction. Why is that?
For example, prove that tree with $n$ vertices has $n-1$ edges. Why would it be wrong to assume $n$ vertices has $n-1$ edges, and then use that to prove $n+1$ vertices has $n$ edges?
It is not wrong to do this. I think in principle it is practically necessary to do this if you use induction formally.
The question is how to do the "then use that to prove" step. If you add a vertex to the tree, you have to prove that no matter how you add the vertex it always adds exactly one edge. Not only that, you have to show that there is not some tree of $n+1$ edges that your method fails to produce.
On the other hand, if you delete a vertex, all you have to do is to demonstrate that for any arbitrary tree of $n+1$ vertices, at least one vertex of the tree has exactly one edge, then you choose that node to delete and show that this reduces the number of edges by exactly one. So the tree with $n+1$ vertices had exactly one more edge than the tree you get after deletion, which has $n$ and therefore $n-1$ edges. And one more than $n-1$ is $n.$
However, I think the rule you were given in class is merely a good guideline or heuristic to follow, rather than an absolute rule of logic. For some problems (possibly including your example), by working carefully and making sure you covered all possible cases, you could show that adding a vertex will always preserve the desired property. I think the advice is based on the observation that people tend to spend more effort and make a lot more mistakes doing "add a vertex" proofs than doing "remove a vertex" proofs.