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 
After checking the basis for the induction we argue as follows: By the lemma 
Student: Now what about the case where
(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
Student: Yes, we proved that, but what about the case where
Me: But I can assume that
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
Me: Look, I can handle the case where
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
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
Student: yes, yes.
Me: (victoriously) ) So we can choose
Student (really victoriously) : And what about the case that
Combinatorics and more 
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.”
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.
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.”
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.
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?
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
and let’s just call it 
for the sake of simplicity.” The student misinterprets that and thinks that you are saying,”Let’s call some vertex (in 
), 
.” Next, the student sees that you have considered the case where 
is a leaf but that you avoided dealing with the case where 
is not a leaf. Of course, in your proof, 
is necessarily a leaf!
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.
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?”
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.
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.
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.
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.’ “
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….
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.
Pingback: In how many ways you can chose a committee of three students from a class of ten students? | Combinatorics and more
@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…
You can call the leaf L instead of V and then it’s likely that it must be a leaf. Better yet, call it “leaf” and then it must be a leaf.
Alternatively, if v is not a leaf, then pick a different vertex v’ which is a leaf …
If this, too, doesn’t help, try a proof by contradiction and then they’ll get stuck somewhere else.