induction proof over graphs

Question

I have a question about how to apply induction proofs over a graph. Let's see for example if I have the following theorem:

Proof by induction that if T has n vertices then it has n-1 edges.

So what I do is the following, I start with my base case, for example:

a=2

v1-----v2

This graph is a tree with two vertices and on edge so the base case holds.

Induction step:

Let's assume that we have a graph T which is a tree with n vertices and n-1 edges (Induction Hypothesis) Now I take a new vertex that is not connected to the tree that I will call it v'. If I add this v' to T then I will have to connect it with any vertex that is on T by an edge to form the new graph T'. By IH hypothesis T has n vertices and n-1 edges, and by adding this new vertex I will end up with n+1 vertices and n edges. As we see the addition of this new vertex v' with its correspondent edge will not form a cycle, so T' will also be a tree.

Is it my induction proof fine? and if its not, then how it will be a sound induction proof?

Thanks

Answer 1

Your induction proof is incorrect; the way induction works is (for example): Suppose we have a sequence $P(1),P(2),\ldots$ of statements and we wish to prove that $P(n)$ is true for all natural numbers $n$. After proving some base cases, say $P(1),\ldots,P(k)$, we consider an arbitrary $n>k$ and prove $P(n)$ assuming that the statements $P(1),P(2),\ldots,P(n-1)$ are all true.

In your case, you must thus assume that $T$ is a tree on $n$ vertices that someone gives to you and you must prove that it has $(n-1)$ edges by assuming that all smaller trees satisfy the hypothesis. Instead, in your proof, you have taken some tree on $(n-1)$ vertices and added a vertex to get some tree on $n$ vertices. To get a correct proof, show that $T$ must contain a leaf vertex $v$, and then delete $v$, and show that $T \setminus \{v\}$ is also a tree. You can apply the induction hypothesis to this smaller tree.

Answer 2

In response to a comment you made on Aravind's answer, you are absolutely allowed to go from $n$ to $n+1$, that is not where the problem in your proof is. However, your proof is still not working completely.

What you have done is taken an arbitrary tree on $n$ vertices, which by your induction hypothesis has $n-1$ edges. You now form a new tree, (not an arbitrary tree!!) by adding a vertex and an edge. Indeed, this new tree satisfies the property trying to be proven. However, you have not shown this in general. If you want to go this route, you must be more rigorous. It would be necessary to show that the only way to form a tree (by adding one vertex) from your tree on $n$ vertices is to add a single edge. Indeed, this is the case, adding any two edges from a vertex to a tree will clearly create a cycle, and adding no edges will clearly create a forest. However, this last statement is missing from the proof.

To reiterate, you must show that an arbitrary tree on $n+1$ vertices satisfies the property, not just some tree on $n+1$ vertices that can be obtained from a tree on $n$ vertcies. Typically, especially from my experience with graph theory, you start with the graph whose property you're trying to prove, then remove a vertex or some structure to produce a smaller graph which is covered by the induction hypothesis. This is instead of starting with a graph which satisfies the induction hypothesis and then moving to a larger graph. Hopefully, I have fleshed out why the latter option does not work as well.