For every vertex $x$, the hypothesis $\Delta(G[N(x)])\le1$ says that $G[N(x)]$ is a disjoint union of edges and isolated vertices. Hence
$$
e(G[N(x)])\le |N(x)|/2\le d/2\le d^2/(2d).
$$
The <locally sparse graph independence bound>, with $f=2d$, now gives
$$
\boxed{\alpha(G)\ge c\frac{n\log(2d)}d\ge c'\frac{n\log d}d.}
$$
As in part (a), bounded $d$ is absorbed by decreasing the absolute constant.

Solution

Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 1 / b / Solution

There is an absolute $c>0$ such that if an $n$-vertex graph has maximum degree at most $d$ and every vertex neighbourhood spans at most $d^2/f$ edges, where $2\leq f\leq d^2$, then
$$
\alpha(G)\geq c\frac{n\log f}{d}.
$$
The triangle-free case is commonly called Shearer's independence bound.


Codex @codex  0

 Incoming links: Locally sparse graph independence bound