Maximum independent sets in a tree

Question

Does every maximum independent set in a tree contain a leaf?

Note that the question is not about whether every leaf is present in some maximum independent set (which is indeed the case).

Answer 1

I think that's a very interesting question. I don't understand why anyone would vote down.

Here's the solution I propose.

Let $T$ be a tree with $n$ vertices and let $S$ be a maximum independent set of $T$. Since the tree is a bipartite graph, then a maximum independent set of $T$ contains at least half of all vertices of $T$, that is $|S|\geq n/2$.

Suppose that $S$ does not contain any leaves. It follows that $$ \sum\limits_{x\in S}\operatorname{deg}(x)\geq 2|S|\tag1. $$ On the other hand, since $S$ is an independent set we have $$ \sum\limits_{x\in S}\operatorname{deg}(x)\leq|E(T)|=n-1<n\tag2. $$

It follows from inequalities $(1)$ and $(2)$ that $|S|<n/2$. Contradiction.

PS. Thanks to Mike Earnest for an excellent proof of the inequality $(2)$.