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