The Five-Cycle and the Erdős-Hajnal Property

For each $i$, let $P_i$ be the set of vertices in $D$ adjacent to $a_i$ and to none of $a_1,\dots ,a_{i-1}$. By the second hypothesis, $\mathrm{\mid }{P}_i\mathrm{\mid }\ge (2\mathrm{/}3{)}^s\mathrm{\Delta }$, and the sets $P_1,\dots ,P_k$ are pairwise disjoint. Let $Q_i$ be the set of vertices in $D\setminus P_i$ adjacent to $a_i$. Since every vertex of $A$ has at most $(2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }$ neighbours in $D$, we have $\mathrm{\mid }{Q}_i\mathrm{\mid }\le (2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }-(2\mathrm{/}3{)}^s\mathrm{\Delta }=(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2$.

Declare the vertices $a_k,a_{k-1},\dots ,a_1$ good backwards as follows: $a_i$ is good when at most $\mathrm{\mid }{P}_i\mathrm{\mid }\mathrm{/}2$ vertices of $P_i$ are adjacent to a good vertex among $a_{i+1},\dots ,a_k$. Let $I$ be the set of good indices, and let $Q:={\bigcup }_{i\in I}{Q}_i$. For every bad index $i\mathrm{\notin }I$, at least $\mathrm{\mid }{P}_i\mathrm{\mid }\mathrm{/}2\ge (2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2$ vertices of $P_i$ lie in $Q$. Since the $P_i$ are disjoint and each $Q_i$ has size at most $(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2$, it follows that $(k-\mathrm{\mid }I\mathrm{\mid })(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2\le \mathrm{\mid }Q\mathrm{\mid }\le \mathrm{\mid }I\mathrm{\mid }(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2$, so $\mathrm{\mid }I\mathrm{\mid }\ge k\mathrm{/}2$.

If $I\mathrm{\ne }\mathrm{\varnothing }$, then for each $i\in I$ let $B_i:=P_i\setminus Q$. We have $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \mathrm{\mid }{P}_i\mathrm{\mid }\mathrm{/}2\ge (2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2$. If $i<j$ are both in $I$, then $B_i$ is disjoint from $P_j$ and every vertex of $B_i$ avoids $Q_j$, so no vertex of $B_i$ is adjacent to $a_j$; similarly no vertex of $B_j$ is adjacent to $a_i$. Therefore $((a_i,B_i):i\in I)$ is a $(\mathrm{\mid }I\mathrm{\mid },(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2)$-comb in $(A,B)$ by [L1].

If $I\mathrm{\ne }\mathrm{\varnothing }$ and $(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2\ge \mathrm{\Gamma }\mathrm{\mid }I{\mathrm{\mid }}^{-1\mathrm{/}d}$, then step 3.1 already gives the first alternative. Hence we may assume either $I=\mathrm{\varnothing }$ or $(2\mathrm{/}3{)}^s\mathrm{\Delta }\mathrm{/}2<\mathrm{\Gamma }\mathrm{\mid }I{\mathrm{\mid }}^{-1\mathrm{/}d}$. In the second case, $\mathrm{\mid }I\mathrm{\mid }<(2\mathrm{\Gamma }(3\mathrm{/}2{)}^s\mathrm{/}\mathrm{\Delta }{)}^d$. When $I=\mathrm{\varnothing }$, step 2.1 gives $k=0$, so then $C=\mathrm{\varnothing }$. In either remaining case, $k\le 2(2\mathrm{\Gamma }(3\mathrm{/}2{)}^s\mathrm{/}\mathrm{\Delta }{)}^d$.

Since every $a_i$ has at most $(2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }$ neighbours in $D$, the set $C$ of all vertices of $D$ adjacent to one of the $a_i$ satisfies $\mathrm{\mid }C\mathrm{\mid }\le k(2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }\le 2(2\mathrm{\Gamma }(3\mathrm{/}2{)}^s\mathrm{/}\mathrm{\Delta }{)}^d(2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }=2^{d+1}(2\mathrm{/}3{)}^{s-sd-1}{\mathrm{\Gamma }}^d{\mathrm{\Delta }}^{1-d}$. This is the second alternative.

Define pairwise disjoint sets $C_1,C_2,\dots$ inductively. Set $D_1:=B$, and after defining $C_1,\dots ,C_{s-1}$ let $D_s:=B\setminus (C_1\cup \cdots \cup C_{s-1})$. Choose distinct vertices $a_1,\dots ,a_k\in A$ with $k$ maximal such that for each $i$ there are at least $(2\mathrm{/}3{)}^s\mathrm{\Delta }$ vertices of $D_s$ adjacent to $a_i$ and to none of $a_1,\dots ,a_{i-1}$. Let $C_s$ be the set of vertices of $D_s$ adjacent to one of $a_1,\dots ,a_k$. By maximality of $k$, every vertex of $A$ has at most $(2\mathrm{/}3{)}^s\mathrm{\Delta }$ neighbours in $D_s\setminus C_s$. Inducting on $s$ shows that every vertex of $A$ has at most $(2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }$ neighbours in $D_s$.

Every vertex of $B$ belongs to some layer $C_s$. Indeed, if some $b\in B$ survived in every $D_s$, choose a neighbour $a\in A$ of $b$. Then $a$ has at least one neighbour in each $D_s$, contradicting step 1.1 for all large $s$ because $(2\mathrm{/}3{)}^{s-1}\mathrm{\Delta }<1$ eventually. Thus $B=C_1\bigsqcup C_2\bigsqcup \cdots$.

Fix $s\ge 1$. The data $D_s$ and the chosen vertices $a_1,\dots ,a_k$ satisfy the hypotheses of [L1]. Therefore either [L1] already yields a $(t,\mathrm{\Gamma }{t}^{-1\mathrm{/}d})$-comb in $(A,B)$, or $\mathrm{\mid }{C}_s\mathrm{\mid }\le 2^{d+1}(2\mathrm{/}3{)}^{s-sd-1}{\mathrm{\Gamma }}^d{\mathrm{\Delta }}^{1-d}$. So if the first alternative never occurs, the displayed bound holds for every $s$.

Put $q:=(2\mathrm{/}3{)}^{1-d}$. Since $d\in (0,1)$, we have $0<q<1$, and $(2\mathrm{/}3{)}^{s-sd-1}=(3\mathrm{/}2{)}^d{q}^{s-1}$. Hence [L2] gives ${\sum }_{s\ge 1}(2\mathrm{/}3{)}^{s-sd-1}=(3\mathrm{/}2{)}^d{\sum }_{n\ge 0}{q}^n=(3\mathrm{/}2{)}^d\mathrm{/}(1-(2\mathrm{/}3{)}^{1-d})$. Using the disjoint union from step 2.1 and the layer bound from step 2.2, we obtain $\mathrm{\mid }B\mathrm{\mid }={\sum }_{s\ge 1}\mathrm{\mid }{C}_s\mathrm{\mid }\le 2^{d+1}{\mathrm{\Gamma }}^d{\mathrm{\Delta }}^{1-d}{\sum }_{s\ge 1}(2\mathrm{/}3{)}^{s-sd-1}=\frac{2^{d+1}(3\mathrm{/}2{)}^d}{1-(2\mathrm{/}3{)}^{1-d}}{\mathrm{\Gamma }}^d{\mathrm{\Delta }}^{1-d}=\frac{3^{d+1}}{3\mathrm{/}2-(3\mathrm{/}2{)}^d}{\mathrm{\Gamma }}^d{\mathrm{\Delta }}^{1-d}$.

Therefore either the comb alternative occurs at some stage, or the displayed bound on $\mathrm{\mid }B\mathrm{\mid }$ holds. This is exactly the Statement.

If $\delta >1$, then no nonempty graph can have a subset $X\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }$, so the theorem is vacuous. Hence we may assume $\delta \le 1$. Choose ${\tau }_0\in (0,1\mathrm{/}2)$ so small that $\frac{2^{1-1\mathrm{/}{\tau }_0}}{\delta }+(ϵ+\frac{19}{20})(ϵ\delta {)}^{-{\tau }_0}<1$. Because $ϵ\delta <1\mathrm{/}20<1$, decreasing $\tau$ decreases both summands, so the same inequality holds for every $0<\tau \le {\tau }_0$.

By [L1], $\kappa (G)<\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$. Since $\kappa (G)$ is a positive integer for every nonempty graph, it cannot equal $1$: otherwise [L2] would force $\alpha (G)=\omega (G)=1$, hence $\mathrm{\mid }V(G)\mathrm{\mid }=1$, contradicting $1<1^{\tau }$. Therefore $\kappa (G)\ge 2$, so $2<\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$ and hence $\mathrm{\mid }V(G)\mathrm{\mid }>2^{1\mathrm{/}\tau }$.

Set $X_0:=X$. As long as $X_{i-1}\mathrm{\ne }\mathrm{\varnothing }$, choose a vertex $v_i\in X_{i-1}$ of maximum degree in $G[X_{i-1}]$, let $A_i:=N_{G[X_{i-1}]}(v_i)$, choose a stable set $C_i\subseteq A_i$ with $\mathrm{\mid }{C}_i\mathrm{\mid }\ge \mathrm{\mid }{A}_i{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)$, and let $X_i$ be the set of vertices in $X_{i-1}\setminus \{v_i\}$ with no neighbour in $\{v_i\}\cup C_i$. This is possible because when $A_i\mathrm{\ne }\mathrm{\varnothing }$, the induced subgraph $G[A_i]$ is proper, so [L1] and [L2] give $\alpha (G[A_i])\ge \kappa (G[A_i])\mathrm{/}\omega (G)\ge \mathrm{\mid }{A}_i{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)$. The process stops after finitely many steps because $v_i\mathrm{\notin }{X}_i$, so $\mathrm{\mid }{X}_i\mathrm{\mid }<\mathrm{\mid }{X}_{i-1}\mathrm{\mid }$ whenever $X_{i-1}\mathrm{\ne }\mathrm{\varnothing }$.

For $i<j$, the set $X_j$ is contained in $X_i$, so by construction there are no edges from $\{v_i\}\cup C_i$ to $X_j$. Hence $v_1,\dots ,v_s$ are pairwise nonadjacent, and $C_1\cup \cdots \cup C_s$ is stable. For each $i$, let $D_i$ be the set of vertices in $X_{i-1}\setminus (A_i\cup \{v_i\})$ that have a neighbour in $C_i$. Then $X=\{v_1,\dots ,v_s\}\bigsqcup A_1\bigsqcup \cdots \bigsqcup A_s\bigsqcup D_1\bigsqcup \cdots \bigsqcup D_s$, because every vertex removed when passing from $X_{i-1}$ to $X_i$ is either $v_i$, a neighbour of $v_i$, or a vertex outside $A_i\cup \{v_i\}$ with a neighbour in $C_i$.

Put $\gamma :=\delta \mathrm{/}(400ϵ)$. Fix $1\le i\le s$. If $A_i=\mathrm{\varnothing }$, then $C_i=\mathrm{\varnothing }$ and therefore $D_i=\mathrm{\varnothing }$, so certainly $\mathrm{\mid }{D}_i\mathrm{\mid }\le 19\sqrt{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)}$. Assume now that $A_i\mathrm{\ne }\mathrm{\varnothing }$. Every vertex of $D_i$ has a neighbour in $C_i$ by definition, and every vertex of $C_i$ has at most $\mathrm{\mid }{A}_i\mathrm{\mid }$ neighbours in $D_i$ because $v_i$ has maximum degree in $G[X_{i-1}]$ and $\mathrm{\mid }{A}_i\mathrm{\mid }={\mathrm{deg}}_{G[X_{i-1}]}(v_i)$. Apply [L3] to the bipartite graph between $C_i$ and $D_i$ with $\mathrm{\Gamma }:=\gamma \mathrm{\mid }X\mathrm{\mid }\mathrm{/}\delta =\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)$, $\mathrm{\Delta }:=\mathrm{\mid }{A}_i\mathrm{\mid }$, and $d:=1\mathrm{/}2$. If [L3] yields a $(t,\mathrm{\Gamma }{t}^{-2})$-comb $((a_j,B_j):1\le j\le t)$ in $(C_i,D_i)$, then the blocks lie in $X$, the teeth lie in the stable set $C_i$, and $v_i$ is adjacent to every tooth and anticomplete to every block. Thus [L4] gives a rooted stable-tooth comb in $G[X]$. Also $t\mathrm{\Gamma }{t}^{-2}\le \mathrm{\mid }X\mathrm{\mid }$ because the $t$ disjoint blocks lie in $X$, so $t\ge 1\mathrm{/}(400ϵ)$, and $\mathrm{\Gamma }{t}^{-2}=\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵt^2)\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}(400ϵt^2)$. Therefore the theorem is proved in this case. We may hence assume instead that $\mathrm{\mid }{D}_i\mathrm{\mid }\le \frac{3^{3\mathrm{/}2}}{3\mathrm{/}2-(3\mathrm{/}2{)}^{1\mathrm{/}2}}\sqrt{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)}\le 19\sqrt{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }X\mathrm{\mid }\mathrm{/}(400ϵ)}$. This bound now holds for every $1\le i\le s$.

Let $x_i:=\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$. Since $C_1\cup \cdots \cup C_s$ is stable by step 2.1, its size is at most $\alpha (G)$. On the other hand, step 1.3 and [L1] give $\mathrm{\mid }{C}_i\mathrm{\mid }\ge \mathrm{\mid }{A}_i{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)=x_i^{\tau }\mathrm{\mid }X{\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)\ge (x_i\delta {)}^{\tau }\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }\mathrm{/}\omega (G)>(x_i\delta {)}^{\tau }\alpha (G)$. Summing over $i$ and dividing by $\alpha (G)$ yields ${\sum }_{i=1}^s{x}_i^{\tau }<{\delta }^{-\tau }$.

Since $v_1,\dots ,v_s$ are stable by step 2.1, we have $\frac{s}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{\alpha (G)}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{\kappa (G)}{\mathrm{\mid }X\mathrm{\mid }}<\frac{\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau -1}}{\delta }<\frac{2^{1-1\mathrm{/}\tau }}{\delta }$, where the last inequality uses step 1.2.

Because $X_{i-1}\subseteq X$ and $v_i$ has maximum degree in $G[X_{i-1}]$, we have $x_i=\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }\le ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }\le ϵ$. Hence ${\sum }_{i=1}^s{x}_i={\sum }_{i=1}^s{x}_i^{\tau }{x}_i^{1-\tau }\le {ϵ}^{1-\tau }{\sum }_{i=1}^s{x}_i^{\tau }\le ϵ(ϵ\delta {)}^{-\tau }$, and, because $\tau <1\mathrm{/}2$, ${\sum }_{i=1}^s{x}_i^{1\mathrm{/}2}={\sum }_{i=1}^s{x}_i^{\tau }{x}_i^{1\mathrm{/}2-\tau }\le {ϵ}^{1\mathrm{/}2-\tau }{\sum }_{i=1}^s{x}_i^{\tau }\le {ϵ}^{1\mathrm{/}2}(ϵ\delta {)}^{-\tau }$.

Divide the partition identity in step 2.1 by $\mathrm{\mid }X\mathrm{\mid }$. Using step 3.1 and the bound on $\sum x_i^{1\mathrm{/}2}$ from step 4.1, we obtain $1=\frac{s}{\mathrm{\mid }X\mathrm{\mid }}+{\sum }_{i=1}^s{x}_i+{\sum }_{i=1}^s\frac{\mathrm{\mid }{D}_i\mathrm{\mid }}{\mathrm{\mid }X\mathrm{\mid }}\le \frac{s}{\mathrm{\mid }X\mathrm{\mid }}+ϵ(ϵ\delta {)}^{-\tau }+\frac{19}{20}{ϵ}^{-1\mathrm{/}2}{\sum }_{i=1}^s{x}_i^{1\mathrm{/}2}\le \frac{s}{\mathrm{\mid }X\mathrm{\mid }}+(ϵ+\frac{19}{20})(ϵ\delta {)}^{-\tau }$. Combining this with steps 1.1 and 3.3 gives $1<\frac{2^{1-1\mathrm{/}\tau }}{\delta }+(ϵ+\frac{19}{20})(ϵ\delta {)}^{-\tau }<1$, a contradiction. Therefore the comb outcome in step 3.1 must occur, and that outcome yields exactly the rooted stable-tooth comb asserted in the Statement.

If $m=1$, then any single vertex set $X$ works, because a one-vertex graph has maximum degree $0=4ϵ(m-1)$.

If $ϵ=0$, then $G$ has no edges, so any $m$-vertex set $X$ has maximum degree $0=4ϵ(m-1)$. Hence we may assume from now on that $m\ge 2$ and $ϵ>0$. Average the edge count over all $(2m-1)$-vertex subsets $Y\subseteq V(G)$. Some such $Y$ satisfies $e(G[Y])\le ϵ(2m-1)(m-1)$, because the expected edge count in a random $(2m-1)$-subset is exactly the global edge count multiplied by the probability that both endpoints of a given edge are chosen.

In this chosen set $Y$, fewer than $m$ vertices have degree greater than $4ϵ(m-1)$. Otherwise at least $m$ vertices would contribute more than $4ϵ(m-1)$ each to the degree sum, giving $2e(G[Y])>4ϵm(m-1)>2ϵ(2m-1)(m-1)$, contrary to step 1.2.

Delete all vertices of $Y$ whose degree in $G[Y]$ exceeds $4ϵ(m-1)$. By step 2.1 at least $m$ vertices remain; choose any $m$ of them and call the resulting set $X$. Every vertex of $G[X]$ has degree at most its degree in $G[Y]$, so $\mathrm{\Delta }(G[X])\le 4ϵ(m-1)$.

This $X$ has the required size and degree bound.

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 }$.

By [L1], the edges $v{a}_i$, $v{a}_j$, $a_i{b}_i$, $a_j{b}_j$, and $b_i{b}_j$ are present. The same definition excludes every other edge among $\{v,a_i,b_i,b_j,a_j\}$: the teeth $a_i,a_j$ are nonadjacent, the root $v$ is anticomplete to the blocks, and each tooth is anticomplete to the other tooth's block.

Therefore the cyclic order $v-a_i-b_i-b_j-a_j-v$ uses exactly the edges of the induced subgraph on $\{v,a_i,b_i,b_j,a_j\}$. By [L2], that induced subgraph is a copy of $C_5$.

Choose $ϵ$ with $0<ϵ<1\mathrm{/}400$. Apply [L1] with $H=C_5$ and this $ϵ$ to obtain ${\delta }_0>0$. Set $\delta :=\min \{{\delta }_0,1\}\mathrm{/}2$. Then every nonempty $C_5$-free graph has a set $X$ with $\mathrm{\mid }X\mathrm{\mid }\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 }$. Let ${\tau }_0$ be the constant from [L2] for this pair $(\delta ,ϵ)$. Because $400ϵ<1$, choose $\tau \in (0,{\tau }_0]\cap (0,1\mathrm{/}2)$ so small that $(400ϵ{)}^{2-1\mathrm{/}\tau }>400ϵ\mathrm{/}\delta$.

Suppose for contradiction that some nonempty $C_5$-free graph satisfies $\kappa (G)<\mathrm{\mid }V(G){\mathrm{\mid }}^{\tau }$. Choose such a graph of minimum order. Then [L4] makes it $\tau$-critical.

Apply the last sentence of step 1.1 to this minimal counterexample. There is a set $X\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }\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 }$. If the low-degree graph is $\bar{G}[X]$, replace $G$ by its complement. This preserves the order, preserves $\kappa$ because complement swaps cliques and stable sets, preserves $\tau$-criticality because induced subgraphs and complements commute, and preserves $C_5$-freeness because $C_5\cong \overline{C_5}$. So after this replacement we may assume that $G[X]$ itself has maximum degree at most $ϵ\delta \mathrm{\mid }V(G)\mathrm{\mid }$.

Apply [L2] to the $\tau$-critical graph $G$ and the set $X$. We obtain a rooted stable-tooth comb $(v,((a_i,B_i):1\le i\le t))$ in $G[X]$ such that $t\ge 1\mathrm{/}(400ϵ)$ and $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \delta \mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}(400ϵt^2)$ for each $i$. If some block $B_i$ meets another block $B_j$ by an edge, then [L3] gives an induced $C_5$ in $G$, impossible. Therefore the blocks $B_1,\dots ,B_t$ are pairwise anticomplete.