1
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ 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$. $\endgroup$ Commented Oct 28, 2022 at 17:06
  • 1
    $\begingroup$ Thank you! That makes sense. $\endgroup$
    – Altricono
    Commented Oct 28, 2022 at 17:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .