A Proof by Induction with a Difficulty

from gilkalai.wordpress.com
Ref : http://gilkalai.wordpress.com/2009/07/22/a-proof-by-induction-with-a-difficulty/

By Gil Kalai

 

The time has come to prove that the number of edges in every finite tree is one less than the number of vertices (a tree is a connected graph with no cycle). The proof is by induction, but first you need a lemma.

Lemma: Every tree with at least two vertices has a leaf.

A leaf is a vertex with exactly one neighbor.

Well, you start from a vertex and move to a neighbor, and unless the neighbor is a leaf you can move from there to a different neighbor and go on. Since there are no cycles and the tree is finite you must reach a leaf. Of course you describe the argument in greater detail and it seems that everybody is happy.

Good.

Theorem: A tree   with vertices has edges.

After checking the basis for the induction we argue as follows: By the lemma has a leaf and once we delete  and the edge containing it we are left with a graph on vertices. Now, has no cycles since did not have any. It takes some effort to show that is connected. You describe it very carefully. Once this is done you know that is a tree as well and you can apply the induction hypothesis.

Student: Now what about the case where is not a leaf?

(In square brackets what I and the students are thinking.)

Me: [I have been here before. There is no way out, just like getting to North Beacon street in Boston] You see, we proved that every tree has a vertex which is a leaf, so we can use this vertex in the proof.

Student: Yes, we proved that, but what about the case where is not a leaf?

Me: But I can assume that is a leaf in the proof. I can choose to be the leaf.

Student: You said several time that in a proof we have to check all the cases [yes, you can assume whatever you want, you are the teacher]. So what about the case where is not a leaf.

Me: Look, I can handle the case where is not a leaf…

Student: [At last. Now you are talking. Explain how you handle it and we can go home] 

Me: It is a bit complicated.

Many students: [So this is why you did not want to deal with it from the beginning; it is complicated.]

Some students realize that I can assume that is a leaf but enjoy seeing the teacher sweating. Some students don't care. Some students believe that the truth, as usual, is somewhere in the middle.  

Me: But the main point in that I do not need to deal with this case. [pray hard now]

Student: [Here you go again] Why?

Me: Because in the proof we can assume that is a leaf since we already proved that every tree has a leaf! Didn't we?

Student:  yes, yes.

Me: (victoriously) ) So we can choose  to be the leaf!!

Student (really victoriously) : And what about the case that is not a leaf?!!

 

View Larger Map