3
$\begingroup$

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.2012-11-24
  • 0
    How is it possible to have cycles in a forest ?2012-11-24
  • 1
    @EuYu All you're missing is that I'm bad at graph theory. :) That is a great short proof.2012-11-24
  • 0
    @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?2012-11-24
  • 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.2012-11-24
  • 0
    Here is a result which may be of interest to you. The wikipedia article on [triangle-free graphs](http://en.wikipedia.org/wiki/Triangle-free_graph) say that $\sqrt{n}$ is a lower bound for the independence number of a triangle free graph. This will immediately prove that the only graphs with girth $4$ without an independent set of size $3$ is the $4$-cycle. Again, I do not know how well this will generalize.2012-11-24
  • 0
    @EuYu Can this be right? Wouldn't that imply that the $5$-cycle has independence number 3?2012-11-24
  • 0
    That'll teach me to trust wiki! Perhaps it's a floor instead of a ceil. In either case, I will look into it a bit more.2012-11-24
  • 0
    OK, I've read the proof a bit more carefully and it seems solid with one exception. If there exists a vertex with maximum degree greater than or equal $\sqrt{n}$ then it's neighborhood is an independent set, so $\alpha \ge \sqrt{n}$. Otherwise, $\Delta < \sqrt{n}$. The next step in the proof implicitly uses Brooke's theorem. A triangle free graph is obviously not complete but it may be a cycle. So for all **non-cycle** triangle-free graphs, we have $$\chi \le \Delta \implies \alpha \ge \frac{n}{\chi} \ge \frac{n}{\Delta} > \sqrt{n}$$2012-11-24

1 Answers 1

5

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

  • 0
    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.52016-06-17