I have seen some proofs on this website for this problem using degree counting, but I was wondering if we could use induction?
My proof is as follows:
Base Case: $n = 2$ vertices Here, the number of leaves is 2 and the maximum degree $k$ in the tree is 1. Thus, the claim holds true.
Inductive Hypothesis: Assume the claim holds for trees of size $n$ vertices.
Inductive Step: WTS Claim holds for trees of size $n+1$ vertices
Suppose we have some tree $T$ on $n$ vertices with max degree $k$. By IH, $T$ has at least $k$ leaves. Suppose we add a leaf to $T$ to create $T'$, some tree with $n+1$ vertices. We now have two cases:
(1) The max degree of $T'$ is still $k$, in which case we are done. (2) The max degree of $T'$ increases. The max degree can only increase by 1 because we are only adding one vertex/edge to $T$. So, the claim still holds true and we are done.
Yep, that's my proof. I have a bad feeling that I am overlooking some facts when I came up with this. Could someone let me know? This is not a homework problem, just preparing for an exam. Thanks!
As specified in the comment, you need to reverse your induction, going from any tree on $n+1$ to a tree on $n$ vertices.
Otherwise you need to argue that you cover all possible $n+1$ trees by your construction.
Here you are only showing that from a $n$-tree satisfying the hypothesis, you can build a ($n+1$)-tree also satisfying the hypothesis. Your are not prooving that any $(n+1)$-tree satisfies the hypothesis.
The general reasoning stays the same in this reverse construction.