Consider a triangle-free graph $G$. The notations used are:
- $\alpha(G) = $ the size of a largest independent set of $G$.
- $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!
Thanks in advance!