# Can someone check my proof for: If a tree T has maximum degree k, then it has at least k leaves.

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!

• In th einduction step, it would be more stringent to start with an arbitrary (!) tree with $n+1$ vertices and then transfrom this to a tree with $n$ vertices by removing a leaf – Hagen von Eitzen Feb 14 '19 at 19:22

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.