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

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?

-

4
I might be missing something here but this seems too simple. Take a bipartite coloring of your forest and take the largest color cover. – EuYu Nov 24 '12 at 19:47
How is it possible to have cycles in a forest ? – Amr Nov 24 '12 at 19:56

1
@EuYu All you're missing is that I'm bad at graph theory. :) That is a great short proof. – Alexander Gruber Nov 24 '12 at 20:23
@EuYu Can your method with color coverings be generalized to graphs of finite girth? For example, could it be used to show that the only graphs with girth $4$ without an independent set of size $3$ is the $4$-cycle? – Alexander Gruber Nov 24 '12 at 20:41

1
The argument is dependent more on the fact that forests are bipartite than on their girth. I'm not sure it will generalize nicely for girths. The most general result I could give is that if a graph of order $n$ is $k$-chromatic, then there is an independent set of at least $\frac{n}{k}$. This is a well-known trivial bound on the independence number. – EuYu Nov 24 '12 at 20:53
show 4 more comments

## 1 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)$

-

Perfect, thank you. – Alexander Gruber Nov 24 '12 at 20:08
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 16, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.93829345703125, "perplexity_flag": "head"}