Every tree has at least two vertices and at least two leaves. Prove by induction.

Steps to Solve

1. Base Case We start by checking the smallest case of a tree. A tree with one vertex (the root) has 1 vertex and 0 leaves. Thus, consider a tree with 2 vertices: one root and one child. In this case, we have:

• Number of vertices = 2
• Number of leaves = 1

This validates that a tree with 2 vertices meets the condition of having at least 2 vertices.

2. Induction Hypothesis Now assume that for a tree with $n$ vertices, the statement holds true; that is, the tree has at least 2 leaves.

3. Induction Step We need to show that if the statement is true for $n$ vertices, it must also be true for $n + 1$ vertices. Suppose you have a tree with $n$ vertices. To create a tree with $n + 1$ vertices, you can add another vertex to any existing leaf of the tree.

• After adding this vertex, the original leaf becomes an internal node.
• Therefore, the number of leaves will increase by 1.

If the original tree had at least 2 leaves before adding the new vertex, it still maintains at least 2 leaves after the addition.

4. Conclusion of the Induction By our base case, we established that a tree with 2 vertices has at least 2 vertices. By the induction step, if a tree with $n$ vertices has at least 2 leaves, then a tree with $n + 1$ vertices also has at least 2 leaves.

Thus, by the principle of mathematical induction, every tree with at least 2 vertices must also have at least 2 leaves.