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!

Thanks in advance!


1 Answer 1


If you don't care about the constants, then the answer is 'yes' by an easy reduction:

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.

  • $\begingroup$ Nice one. This indeed is a very useful trick! $\endgroup$ Commented Mar 21, 2014 at 15:49
  • $\begingroup$ Can we obtain any lower bound on the average degree of the graph G' ? $\endgroup$ Commented Mar 29, 2014 at 11:35
  • $\begingroup$ @Bagaria No. If $G$ was a click of size $n/3$ and an additional $2n/3$ isolated vertices, then $G'$ is just isolated vertices. $\endgroup$
    – greg
    Commented Mar 29, 2014 at 13:03
  • $\begingroup$ Any other reduction technique where the max_degree and avg_degree have the same order? $\endgroup$ Commented Mar 29, 2014 at 13:36
  • $\begingroup$ Maybe you can write what the purpose is, rather than properties of the reduction, because when it's not clear what any of this is for, it's hard to give you any useful advice. $\endgroup$
    – greg
    Commented Mar 29, 2014 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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