1

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?

user614287
  • 1,147
CJ Lin
  • 13
  • Nothing wrong. In life, sometimes, is easier to destroy than to create. – Phicar Apr 15 '19 at 20:28
  • 3
    If you start with a tree with $n+1$ vertices and delete a vertex, you know you have handled all possible trees with $n+1$ vertices. If you want to start with a tree with $n$ vertices and add a vertex, you have to argue that any tree with $n+1$ vertices could be the result of this adding procedure (which is not hard, but you might as well have just have started with $n+1$ vertices and then deleted one...) – angryavian Apr 15 '19 at 20:39
  • You have been told correctly, because you have to make sure you can generate any possible graph of interest on $n$ vertices by adding a particular vertex, that is not always possible. – gt6989b Apr 15 '19 at 20:40
  • if he have a tree of $n$ vertices and he took out a vertex to have $n-1$ vertices, he must specify that the vertex he took away is a leaf or not? Since otherwise the new graph of $n-1$ vertices won't be a tree – Fareed Abi Farraj Apr 15 '19 at 21:20
  • @FareedAF Yes, you should specify that you are deleting a leaf. – angryavian Apr 16 '19 at 17:32

1 Answers1

0

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.

David K
  • 98,388