A Proof by Induction with a Difficulty

 

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 T  with n vertices has n-1 edges.

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

Student: Now what about the case where v 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 v which is a leaf, so we can use this vertex in the proof.

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

Me: But I can assume that v is a leaf in the proof. I can choose v 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 v is not a leaf.

Me: Look, I can handle the case where v 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 v 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 v 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 v to be the leaf!!

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

 

About these ads
This entry was posted in Teaching, What is Mathematics and tagged , . Bookmark the permalink.

16 Responses to A Proof by Induction with a Difficulty

  1. JeffE says:

    Answer 1: “This is a theorem about all trees, not about all vertices. So the proof has to handle any possible tree you can think of. But once you pick the tree, I can use any vertex that makes the proof work.”

    Answer 2: “Okay, fine. Suppose v has degree d. Then T-v is a forest of d trees T_1, T_2, …, T_d. Let n_i be the number of nodes in T_i; notice that T has n = sum_i n_i + 1 nodes. The inductive hypothesis implies that T_i has m_i = n_i-1 edges. So the number of edges in T is sum_i m_i + d = sum_i (n_i – 1) + d = sum_i n_i = n-1. Done.”

  2. Mark Meckes says:

    I’m not positive, but I think I’ve encountered this kind of thing before, and I dealt with it (or would deal with it) by saying something like “In the case that v is not a leaf I forget about that v and pick a different v which is a leaf, knowing the lemma tells me I can do so.” One might quibble about the strict correctness of the logic presented there, but I think it makes the point in a way that gets through to some students who might actually be confused about it.

    I also like JeffE’s Answer 1, which essentially says the same thing less glibly.

  3. Vania says:

    My feeling is that students get confused when things are given names. In this case, calling a vertex “v” makes them think that it’s a fixed vertex, when instead we proceed from the lemma (“there exists a leaf”). It’s almost a purely psychological question, I believe, and not a logico-mathematical one. In my attempts to remove this kind of confusion I try to avoid giving names to objects that have a flexible nature in the argument. Or say something like this: the lemma says that there is a leaf — well, let’s call it v. In this way the name *follows* the declaration that it’s a leaf, so the question about when it’s not a leaf is just a bad question (since the lemma ensures the existence of a leaf, so there will always be a vertex we can “call v.”

  4. Kevin C. says:

    Extending Vania’s idea a bit further, why not combine the lemma and the rest of the induction?

    In other words, for the induction step start at an arbitrary vertex, walk along the tree as in the proof of the lemma until you reach a leaf, then remove the vertex you stop at.

    It’s mathematically identical, but this way you make it much easier for the student to identify the leaf in the lemma with the leaf in the main proof.

  5. mpetrache says:

    I think a nice way to speak about this theorem is to give a definition:
    “a move is taking a leaf and cancelling it together with its edge”

    The lemma says “for a finite tree there exist moves”. The theorem says “moves don’t pull you out of the class of trees, they decrease the number of vertices and they preserve [vertices]-[edges]“.

    In this language, proving the theorem becomes “playing the game”, and why we _need_ to deal with leaves is that “to play a game you need to move”. Right?

  6. Vishal Lama says:

    I think the confusion stems from a linguistic misinterpretation, if you will.

    In the proof, what you (the teacher) is simply saying is that “there exists a leaf in T and let’s just call it v for the sake of simplicity.” The student misinterprets that and thinks that you are saying,”Let’s call some vertex (in T), v.” Next, the student sees that you have considered the case where v is a leaf but that you avoided dealing with the case where v is not a leaf. Of course, in your proof, v is necessarily a leaf!

  7. Jack says:

    And I think the confusion is about the student not understanding the quantifiers, which may be because the teacher forgot to state them clearly. This is why JeffE’s answer #1 is so apropos.

    • Gil Kalai says:

      Hi Jack,
      The problem is that it is very difficult to talk to the students about quantifiers. This remind me the following story. When one of my kids was 4 years old a psychologist came to their class to talk to them. After half an hour she had the feeling that the children do not really understand what she was saying. “Children” she asked at that point, “do you understand my terminology?”

  8. shmuel says:

    I like to tell my class at the beginning of the quarter that I will denote by M either a manifold or a module and m means either a point on it or its dimension; H is either homology, cohomology, or a homotpy between a pair of functions, one of which is usually called h. After we homotop a map we continue to call it h. The goal is to abuse notation to the point that you have to follow what the ideas are because you cannot follow just what the words say.

    On the other hand I am rather pedantic in distinguishing Z/p (the cyclic group with p elements) from Fp (the field with p-elements) although notationally I never have distinguish the latter from the free group with p generators. (People could confuse the first two, but no one could ever confuse the second.)

    This necessitates giving up on comparing h with h because that really would be confusing. On the occasions I need to do this, I give in and merely abuse my notation rather than torture it.

    The students seem to be divided among the camps of those that love this and those that hate it.

  9. Gil says:

    Thanks for all the comments. The course where I usually teach this theorem is first year “discrete mathematics”. Courses for first year (undergraduate) mathematics are where students slowly understand what is expected from them when it comes to rigorous mathematical proofs and this is, of course, a delicate process. Actually, the previous two-prizes post is also related to one of the nice topics in this course which is the formula for chosing k elements from a set of n elements with repetitions where the order of choice does not matter. I was quite happy when I came to the conjecture “two decorative rings,” and then, of course, I did not check it.

  10. gowers says:

    A trick that might work for some students would be to label the vertices from 1 to n and then say, “There must be a leaf. Choose the leaf that has smallest label and call it v.” In a sense it doesn’t change anything, but it gives the illusion that you have defined v, rather than picking out a vertex that might conceivably (in the eyes of the student) not be a leaf.

  11. Gil Kalai says:

    Sasha Barvinok mentioned a similar, more basic, story (or a profound philosophical joke according to Wittgenstein) from “Littelwood’s Miscellany”:
    “Schoolmaster: ‘suppose that x is the number of sheep in the problem.’ Pupil: ‘But, Sir, suppose that x is not the number of sheep.’ “

  12. Hillarious. Maybe in my next discrete math exam I will cut and paste the story WITH THE BRACETS
    and ask the students to explain what is wrong with the teacher or the student….

  13. Ehud Friedgut says:

    Wonderful story.
    Personally I think that induction is the root of all evil.
    My favorite approach to teaching this theorem is the following.
    Lemma: adding an edge to a graph, that does not close a cycle, decreases the number of connected components by 1.
    Proof of theorem: Start with the empty graph (n components) and add the edges one by one until
    you have the tree (1 component). How many steps did you take?

    The lemma is also useful for a one line proof that every graph with n vertices and n edges must contain a cycle.

  14. Pingback: In how many ways you can chose a committee of three students from a class of ten students? | Combinatorics and more

  15. Random says:

    @Ehud: Avoiding induction whenever possible is a good idea, except that students are so resistant to it that sometimes I feel I need to use induction even where it is not necessary, to get them used to it.

    Also, I would really like your lemma better if it was stated as: adding an edge that leads to a new vertex…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s