Consider the statement "every non trivial tree has exactly two leaves". The following is an attempted proof of the statement using induction on n, where n the number of vertices. Base case: n=2. The tree is a path, and has exactly two leaves. Inductive hypothesis: Assume that every tree on k vertices has exactly two leaves. Inductive step: Consider a tree T on k vertices. It has exactly two leaves. Add a vertex, make the new vertex adjacent to a leaf of T. Now the new tree has k+1 vertices, and has exactly two leaves. What is wrong with the proof?