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.


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? Continue reading