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!