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

For every vertex $x$, the hypothesis $\Delta (G[N(x)])\le 1$ says that $G[N(x)]$ is a disjoint union of edges and isolated vertices. HenceThe locally sparse graph independence bound, with $f=2d$, now givesAs in part (a), bounded $d$ is absorbed by decreasing the absolute constant.