# Independent set size in triangle-free graphs

Consider a triangle-free graph $G$. The notations used are:

1. $\alpha(G) =$ the size of a largest independent set of $G$.
2. $n(G) =$ the number of vertices in $G$.

Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$,

$$\alpha(G) \geq \frac{n(G)}{8\Delta}\log_2\Delta.$$

The book "Probabilistic Methods" by Alon-Spencer gives a very cute proof in the section "The Probabilistic Lens", (pg 272).

But the theorem is true even when $\Delta$ is subsituted by the average degree $d_{avg}$ in the above expression and Bollobas proves this in his book "Random Graphs, 2nd edition", pg 332, using completely different techniques.

My Question : Can we obtain Bollobas' result by tweaking the technique used by Alon-Spencer?

PS: For a graph theory enthusiasts, both proofs are worth reading!

Take a triangle-free graph $G$ with average degree $d_{avg}$. Create a new graph $G'$ which is obtained from $G$ by deleting all vertices with degree $\ge 2d_{avg}$. Obviously, any independent set in $G'$ is an independent set in $G$, and $G'$ is triangle-free. Also, the number of vertices in $G'$ is at least $n(G)/2$. Now we can apply the Alon--Spencer proof.
• @Bagaria No. If $G$ was a click of size $n/3$ and an additional $2n/3$ isolated vertices, then $G'$ is just isolated vertices. – mobius dumpling Mar 29 '14 at 13:03