Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
@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
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
up vote 5 down vote accepted

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

share|cite|improve this answer
Perfect, thank you. – Alexander Gruber Nov 24 '12 at 20:08
I might be missing something, but what is $\alpha(F)$ ? and how does $3 \leq \alpha(F)$ follow from $5/2 \leq \alpha(F) $ ? since $\alpha (F)$ could equal 2.5 – Curious Jun 17 at 20:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.