This is what I have. I'm pretty sure this is quite incorrect, but am I at least headed in the right direction?
$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.
Assume $P(k)$ is true for some fixed $k$, i.e., the tree on $k$ vertices has at least 2 leaves.
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.