# Maximum independent sets in a tree

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).

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

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

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

• Here's a more conceptual way to prove $(2)$. Imagine placing, for each $x\in S$, a marker on all edges adjacent to $x$. You place $\sum_{x\in S}\text{deg }x$ markers. Since $S$ is independent, no edge gets two markers, so the number of markers is at most the number of edges of $T$, which is $n-1$. Commented Oct 28, 2022 at 17:06
• Thank you! That makes sense. Commented Oct 28, 2022 at 17:49