= Solution
Apply the <Shearer independence bound for a triangle-free graph>. It states that an $n$-vertex <triangle-free graph> of maximum degree at most $d$ has an <independent set> of size
$$
\alpha(G)\ge c\frac{n\log d}{d}
$$
for an absolute $c>0$. The result is immediate for bounded $d$ after reducing $c$, while the theorem gives the asserted logarithmic gain for $d$ large. Thus
$$
\boxed{\alpha(G)\ge c n\log d/d.}
$$
For completeness, the key input in Shearer's proof is to expose a random independent set one degree scale at a time. Triangle-freeness makes every neighbourhood independent, so conditioning on earlier choices creates no edges inside the available neighbours. The expected gain at degree scale $j$ is $\Omega(n_j/d)$; summing over the $\Theta(\log d)$ nonempty scales gives $\Omega(n\log d/d)$. The entropy, or hard-core-model, form of the argument makes this scale calculation rigorous without losing vertices counted at adjacent scales.
Back to article page
