Question

Prove by induction that a tree with at least two vertices has at least two leaves.

Thank you!

Answer 1

• The proof of this theorem using "complete induction" is as follows:

Consider any integer k≥2.Assuming that every tree with at least two but fewer than k vertices has at least two leaves, we prove that every tree with k vertices has at least two leaves.

Let T be a tree with k vertices. Choose a vertex v of T which is not a leaf. (If every vertex is a leaf, there is nothing to prove.) The components of T−v are trees T1,T2,…,Tn. Since T is a tree, v is joined to to exactly one vertex in each Ti. Since v is not a leaf of,T, we have n≥2.

Lastly we have to show that Ti contains at least one vertex which is a leaf of T. On the one hand, if Ti has only one vertex, then that vertex, being joined only to v, is a leaf of T. On the other hand, if Ti has more than one vertex, then by the inductive hypothesis the tree Ti has at least two leaves; at most one of them is joined to v, so at least one of them is a leaf of T.

If you have any queries please ask me.

Thank you so much sir