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!

  • $\begingroup$ 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 $\endgroup$ – 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.

The general reasoning stays the same in this reverse construction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.