An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree

Put $\eta :=ϵ\mathrm{/}8$. If $\eta \ge 1\mathrm{/}2$, then $ϵ\ge 4$. The conclusion is trivial with $\delta :=1$, because every induced subgraph has maximum degree at most $\mathrm{\mid }V(G)\mathrm{\mid }-1<\mathrm{\mid }V(G)\mathrm{\mid }\le ϵ\mathrm{\mid }V(G)\mathrm{\mid }=ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }$. So we may assume $\eta <1\mathrm{/}2$, and [L1] gives ${\delta }_0>0$ for the parameter $\eta$. Set $\delta :=\min \{{\delta }_0,1\}\mathrm{/}2$.

Apply [L1] to the given nonempty $H$-free graph $G$. Then there is $Z\subseteq V(G)$ with $\mathrm{\mid }Z\mathrm{\mid }\ge {\delta }_0\mathrm{\mid }V(G)\mathrm{\mid }\ge 2\delta \mathrm{\mid }V(G)\mathrm{\mid }$ and either $d_G(Z,Z)\le \eta$ or $d_G(Z,Z)\ge 1-\eta$. Let $m:=\lceil \delta \mathrm{\mid }V(G)\mathrm{\mid }\rceil$. Since $\mathrm{\mid }Z\mathrm{\mid }$ is an integer and $\mathrm{\mid }Z\mathrm{\mid }\ge 2\delta \mathrm{\mid }V(G)\mathrm{\mid }$, we have $\mathrm{\mid }Z\mathrm{\mid }\ge \lceil 2\delta \mathrm{\mid }V(G)\mathrm{\mid }\rceil \ge 2m-1$, so $m\le (\mathrm{\mid }Z\mathrm{\mid }+1)\mathrm{/}2$.

First suppose $d_G(Z,Z)\le \eta$. Writing $n:=\mathrm{\mid }Z\mathrm{\mid }$, the definition of density gives $2\mathrm{\mid }E(G[Z])\mathrm{\mid }\mathrm{/}{n}^2\le \eta$. If $n=1$, then $m=1$ and $Z$ itself already has maximum degree $0\le ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }$. If $n\ge 2$, then $n^2\le 2n(n-1)$, so $\mathrm{\mid }E(G[Z])\mathrm{\mid }\le \eta n^2\mathrm{/}2\le (ϵ\mathrm{/}4)n(n-1)\mathrm{/}2$. Applying [L2] with $\lambda =ϵ\mathrm{/}4$ gives a set $X\subseteq Z$ with $\mathrm{\mid }X\mathrm{\mid }=m$ and maximum degree at most $4(ϵ\mathrm{/}4)(m-1)=ϵ(m-1)\le ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }$.

Now suppose instead that $d_G(Z,Z)\ge 1-\eta$. If $n:=\mathrm{\mid }Z\mathrm{\mid }$, then $d_{\bar{G}}(Z,Z)=1-\frac{1}{n}-d_G(Z,Z)\le \eta -\frac{1}{n}\le \eta$. Applying step 3.1 to the complement graph on the same vertex set yields $X\subseteq Z$ with $\mathrm{\mid }X\mathrm{\mid }=m$ such that $\bar{G}[X]$ has maximum degree at most $ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }$.

In either case there is a set $X$ with $\mathrm{\mid }X\mathrm{\mid }=m\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }$ such that one of $G[X]$ or $\bar{G}[X]$ has maximum degree at most $ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }$.