Any forest on 5 or more vertices contains an independent set of size 3.

206 Views Asked by At

I am looking for a short proof of this fact. This is clearly true by drawing these trees, but I am having trouble putting it into writing. Somehow I need to select 3 of the 5 vertices and show that there must be a $3$-cycle or an independent set of size $3$. (Is this a Ramsey number or something like that?)

Is there an obvious/short argument here, or perhaps a lemma I could use to knock it out quickly?

1

There are 1 best solutions below

1
On BEST ANSWER

In general let $F$ be a forest of order $n$ with $k$ connected components. It follows that every connected component is a tree, thus every component is bipartite (because trees do not have odd cycles). Thus the ith connected component contains an independent set of size greater than ceiling($n_i/2$) (Where $n_i$ is the order of the ith connected component) . Since the union of all these independent sets is again independent (because they come from different connected components), thus we have:

$$\sum_{i=1}^k ceiling(n_i/2)\leq \alpha(F)$$

A weaker version of this inequality would be: $$n/2=\sum_{i=1}^k (n_i/2)\leq \alpha(F)$$

Since the order of $F$ in your question is 5, we know that $5/2\leq \alpha(F)$ hence $3\leq \alpha(F)$