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

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/iii/paper-132/1/b/solution