6
$\begingroup$

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

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ I have taken a tree T with n vertices and n-1 edges and not the opposite way around as you claim. For what I know in induction proof one can go from n to n+1 or to proof from n-1 to n $\endgroup$ – Lila Jun 20 '16 at 17:31
  • 3
    $\begingroup$ @Lila One way to see what Aravind is saying is that your proof would be showing that a specific graph, $T'$ grown from a tree $T$ on $n$ vertices by adding one vertex and one edge is also a tree but now with $n+1$ vertices and $n$ edges. The part that you are missing is that you need to show that any tree on $n+1$ vertices can be constructed in such a way. $\endgroup$ – D Poole Jun 20 '16 at 17:43
  • $\begingroup$ @DPoole Had to +1 your comment due to your verbage: grown from a tree $T$... $\endgroup$ – Paddling Ghost Jun 20 '16 at 19:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.