This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction?
Base Case:
$P(2)$: Tree on 2 vertices can only have one edge, the edge connecting the 2 vertices. So both vertices have degree 1, both are leaves, so $P(1)$ is true.
Induction Hypothesis:
Assume $P(k)$ is true for some fixed $k$, i.e., the tree on $k$ vertices has at least 2 leaves.
Induction step:
Show $P(k) \implies P(k + 1)$.
- The tree on $k+1$ vertices is obtained by adding a vertex to the tree with $k$ vertices
- Since trees are connected, we must add an edge connecting the new vertex to one of the existing vertices in the tree.
- Trees are acyclic, so we add an edge from any existing vertex that does not create a cycle
- The new vertex now has degree 1
Hence, using induction, $P(n)$ is true.
Best Answer
I would first prove that every tree has at least one leaf.
Added: You have in fact tacitly assumed this in your first bullet point, when you say that every tree on $k+1$ vertices is obtained by adding a vertex to a tree with $k$ vertices. This requires that you be able to remove a vertex from a tree on $k+1$ vertices and still have a tree. This cannot be guaranteed unless the tree on $k+1$ vertices has a leaf. End addition.
Now your induction step is much easier. You assume $P(k)$ and let $T$ be a tree with $k+1$ vertices. It has a leaf $u$. Remove the leaf and its attached edge; what’s left is a tree with $k$ vertices, so it has two leaves, say $v$ and $w$.