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