Generalized Niceness and Reduction Outcomes

Put $n:=\lceil m\rceil$ and $s:=\lceil ϵn\rceil$. Since every $\mathrm{\mid }{A}_i\mathrm{\mid }$ is an integer at least $m$, one has $n\le \mathrm{\mid }{A}_i\mathrm{\mid }$. Choose independently and uniformly an $n$-element subset $X_i\subseteq A_i$ for each $i$. For a weakly ${ϵ}^a$-sparse pair $(A_i,A_j)$, finite double counting and [L3] give $\mathbb{E}{e}_G(X_i,X_j)=e_G(A_i,A_j)\frac{n^2}{\mathrm{\mid }{A}_i\mathrm{\mid }\mathrm{\mid }{A}_j\mathrm{\mid }}\le {ϵ}^a{n}^2\mathrm{.}$ Consequently the probability that $e_G(X_i,X_j)>{ϵ}^{a-2}{n}^2$ is less than ${ϵ}^2$: on that event the nonnegative edge count already exceeds the threshold, so its expectation is greater than the threshold times the event probability. There are at most $\left(\genfrac{}{}{0px}{}{\mathrm{\ell }}{2}\right)$ relevant pairs, and $\left(\genfrac{}{}{0px}{}{\mathrm{\ell }}{2}\right){ϵ}^2<\frac{1+ϵ}{2}<1$ because $\mathrm{\ell }=\lceil {ϵ}^{-1}\rceil <{ϵ}^{-1}+1$. By [L4], some simultaneous choice of the $X_i$ therefore satisfies $e_G(X_i,X_j)\le {ϵ}^{a-2}{n}^2$ for every weakly sparse pair. Complete pairs remain complete by [L2]. Fix such a choice.

We choose $D_1,\dots ,D_{\mathrm{\ell }}$ successively, always requiring $D_i\subseteq X_i$ and $\mathrm{\mid }{D}_i\mathrm{\mid }=s$. Suppose that $D_1,\dots ,D_{i-1}$ have already been chosen. For each $p\mathrm{\ne }i$ with $(A_p,A_i)$ weakly ${ϵ}^a$-sparse, let $C_p\subseteq X_i$ consist of the vertices having more than ${ϵ}^{a-4}n$ neighbours in $D_p$ when $p<i$, or more than ${ϵ}^{a-4}n$ neighbours in $X_p$ when $p>i$. In either case step 1.1 gives $e_G(X_i,D_p)\le e_G(X_i,X_p)\le {ϵ}^{a-2}{n}^2,$ so $\mathrm{\mid }{C}_p\mathrm{\mid }<{ϵ}^{2}n$. Since $\mathrm{\ell }-1<{ϵ}^{-1}$, the union of the forbidden sets has fewer than $ϵn$ vertices and therefore at most $s-1$ vertices. Thus at least $n-s+1\ge s$ vertices survive: indeed $s\le \lceil n\mathrm{/}4\rceil$ and $2\lceil n\mathrm{/}4\rceil \le n+1$. Choose $D_i$ to be any $s$ survivors.

Let $(A_i,A_j)$ be weakly ${ϵ}^a$-sparse, and assume $i<j$. When $D_i$ was chosen, the index $j$ was still future, so every vertex of $D_i$ has at most ${ϵ}^{a-4}n$ neighbours in $X_j$, hence at most that many in $D_j$. When $D_j$ was chosen, every vertex of $D_j$ was required to have at most ${ϵ}^{a-4}n$ neighbours in $D_i$. Since $s\ge ϵn$, ${ϵ}^{a-4}n\le {ϵ}^{a-5}s\mathrm{.}$ Therefore $D_i$ is ${ϵ}^{a-5}$-sparse to $D_j$ and $D_j$ is ${ϵ}^{a-5}$-sparse to $D_i$.

If $(A_i,A_j)$ is complete, then $(D_i,D_j)$ is complete by [L2] because $D_i\subseteq A_i$ and $D_j\subseteq A_j$. Together with step 3.1, this proves that $\mathcal{D}=(D_1,\dots ,D_{\mathrm{\ell }})$ has all the required properties. ∎

Suppose some block $D_i$ has no anticonnected component of size at least $q\mathrm{/}\mathrm{\ell }$. Partition the anticonnected components of $G[D_i]$ into a minimum number of nonempty unions $S_0,\dots ,S_r$, each of size less than $q\mathrm{/}\mathrm{\ell }$, ordered so that $\mathrm{\mid }{S}_0\mathrm{\mid }\le \cdots \le \mathrm{\mid }{S}_r\mathrm{\mid }$. Since the unions cover $D_i$ and each has size less than $q\mathrm{/}\mathrm{\ell }$, one has $r+1>\mathrm{\ell }$. Minimality implies $\mathrm{\mid }{S}_{t-1}\mathrm{\mid }+\mathrm{\mid }{S}_t\mathrm{\mid }\ge q\mathrm{/}\mathrm{\ell }$ for every $t\ge 1$, for otherwise those two unions could be merged. Hence $\mathrm{\mid }{S}_t\mathrm{\mid }\ge q\mathrm{/}(2\mathrm{\ell })\ge q\mathrm{/}{\mathrm{\ell }}^2$ for every $t\ge 1$, because $\mathrm{\ell }\ge 2$. Distinct anticonnected components are complete to one another by [L1], so distinct unions of them are also complete to one another. Therefore $S_1,\dots ,S_{\mathrm{\ell }}$ form a complete $(\mathrm{\ell },q\mathrm{/}{\mathrm{\ell }}^2)$-blockade, proving outcome 1.

We may therefore assume that every $D_i$ has an anticonnected component $C_i$ of size at least $q\mathrm{/}\mathrm{\ell }$. By [L2], the complement $\overline{G[C_i]}$ is connected. Choose a spanning tree of $\overline{G[C_i]}$, and repeatedly delete leaves until exactly $\lceil q\mathrm{/}\mathrm{\ell }\rceil$ vertices remain. The remaining tree is connected, so the induced subgraph of $\overline{G[C_i]}$ on those vertices is connected as well. Calling that vertex set $B_i$, we have $B_i\subseteq C_i$, $\mathrm{\mid }{B}_i\mathrm{\mid }=\lceil q\mathrm{/}\mathrm{\ell }\rceil$, and $G[B_i]$ anticonnected.

If $(D_i,D_j)$ is complete, then $(B_i,B_j)$ is complete because $B_i\subseteq D_i$ and $B_j\subseteq D_j$. If $(D_i,D_j)$ is mutually $\eta$-sparse, every vertex of $B_i$ has at most $\eta \mathrm{\mid }{D}_j\mathrm{\mid }=\eta q$ neighbours in $D_j$, hence at most $\eta q\le \eta \mathrm{\ell }\mathrm{\mid }{B}_j\mathrm{\mid }$ neighbours in $B_j$ because $\mathrm{\mid }{B}_j\mathrm{\mid }\ge q\mathrm{/}\mathrm{\ell }$; the same argument with $i$ and $j$ exchanged gives the reverse direction. Thus every noncomplete pair is mutually $(\eta \mathrm{\ell })$-sparse.

Step 1.1 yields outcome 1, while steps 2.1 and 3.1 yield outcome 2. Therefore one of the two stated outcomes holds.

Apply [L1] to the blockade $\mathcal{B}$. If it yields a $y^4$-restricted induced subgraph on at least $w$ vertices, then outcome 1 of the present lemma holds immediately.

We may therefore assume that [L1] yields an index $i\in [\mathrm{\ell }]$ for which at most $y\mathrm{\mid }G\mathrm{\mid }$ vertices outside $V(\mathcal{B})$ are mixed on $B_i$. Let $M$ be that exceptional set of mixed outside vertices. Every outside vertex with a neighbour in $B_i$ but not in $M$ has at least $\mathrm{\mid }{B}_i\mathrm{\mid }\mathrm{/}2$ neighbours in $B_i$. Since every vertex of $B_i$ has total degree at most $y\mathrm{\mid }G\mathrm{\mid }$ by [L2], the number of outside vertices with at least $\mathrm{\mid }{B}_i\mathrm{\mid }\mathrm{/}2$ neighbours in $B_i$ is at most $2y\mathrm{\mid }G\mathrm{\mid }$.

Let $Y$ be the set of vertices in $V(G)\setminus V(\mathcal{B})$ that have no neighbours in $B_i$, and let $X:=B_i$. By step 2.1, $\mathrm{\mid }Y\mathrm{\mid }\ge \mathrm{\mid }G\mathrm{\mid }-\mathrm{\mid }V(\mathcal{B})\mathrm{\mid }-\mathrm{\mid }M\mathrm{\mid }-2y\mathrm{\mid }G\mathrm{\mid }\ge \mathrm{\mid }G\mathrm{\mid }-y\mathrm{\mid }G\mathrm{\mid }-y\mathrm{\mid }G\mathrm{\mid }-2y\mathrm{\mid }G\mathrm{\mid }=(1-4y)\mathrm{\mid }G\mathrm{\mid }$. By construction there are no edges between $X$ and $Y$, so [L3] gives that $Y$ is anticomplete to $X$. Because all blocks have size $w$, we also have $\mathrm{\mid }X\mathrm{\mid }=\mathrm{\mid }{B}_i\mathrm{\mid }=w$. Thus outcome 2 holds.

Steps 1.1 and 3.1 prove that one of the two stated outcomes must occur.

Fix constants from [L1], [L2], and [L4], and set $a_1:=a{c}_3$, $a_2:=c_4$, $a_4:=4$, $a_5:=h+4$, and $a_3:=\max \{a(c_1+5),a{c}_8,c_5,4d+1\}$. These choices depend only on $\mathcal{F}$.

If $\mathrm{\mid }G\mathrm{\mid }\le y^{-a_3}$, then any one-vertex induced subgraph of $G$ is $y^4$-restricted and has size at least $y^{a_3}\mathrm{\mid }G\mathrm{\mid }$. So outcome 2 holds.

Suppose $\bar{G}$ is $y$-sparse. Apply [L2] to the family $\mathcal{F}$ inside $\bar{G}$ with the parameter $b=4$. Either $\bar{G}$ has a $y^4$-restricted induced subgraph of size at least $y^{4d+1}\mathrm{\mid }G\mathrm{\mid }$, or there are disjoint sets $X,Y\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }\ge y^{4d+1}\mathrm{\mid }G\mathrm{\mid }$, $\mathrm{\mid }Y\mathrm{\mid }\ge (1-hy)\mathrm{\mid }G\mathrm{\mid }$, and $Y$ anticomplete to $X$ in $\bar{G}$. By [L3], the restricted induced subgraph is also $y^4$-restricted in $G$, and the anticomplete pair in $\bar{G}$ is a complete pair in $G$. Since $a_3\ge 4d+1$ and $a_5\ge h$, this gives outcome 2 or outcome 4 in $G$.

We may therefore assume that $G$ itself is $y$-sparse. Put $ϵ:=y^a$, where $a$ is the witness from [L4]. Because $G$ is $\bar{\mathcal{F}}$-free, [L1] applies to $G$ and $ϵ$. If [L1] produces a clique or stable set of size $({ϵ}^{c_3}\mathrm{\mid }G\mathrm{\mid }{)}^{c_4}$, then this is exactly outcome 1 by the choice $a_1=a{c}_3$ and $a_2=c_4$. If [L1] produces a complete or anticomplete $(k,\mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{c_5})$-blockade with $k\ge {ϵ}^{-c_6}$, then $k\ge y^{-1}$ because $c_6\ge 1$, and $\mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{c_5}\ge \mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{a_3}$ because $a_3\ge c_5$, so outcome 3 holds. If [L1] produces an ${ϵ}^{c_7}$-restricted induced subgraph of size at least ${ϵ}^{c_8}\mathrm{\mid }G\mathrm{\mid }$, then ${ϵ}^{c_7}\le y^4$ and ${ϵ}^{c_8}=y^{a{c}_8}\ge y^{a_3}$, so outcome 2 holds. We are left only with the blockade alternative from [L1].

Thus $G$ has a blockade $\mathcal{A}=(A_1,\dots ,A_{\mathrm{\ell }})$ with $\mathrm{\ell }=\lceil {ϵ}^{-1}\rceil$, each $\mathrm{\mid }{A}_i\mathrm{\mid }\ge m:={ϵ}^{c_1}\mathrm{\mid }G\mathrm{\mid }$, and every distinct pair complete or weakly ${ϵ}^{c_2}$-sparse. Apply [L5] to obtain equal-sized subblocks $\mathcal{D}=(D_1,\dots ,D_{\mathrm{\ell }})$ with $\mathrm{\mid }{D}_i\mathrm{\mid }=q:=\lceil ϵ\lceil m\rceil \rceil$ and every noncomplete pair mutually ${ϵ}^{c_2-5}$-sparse. Then apply [L6] to $\mathcal{D}$. If [L6] yields a complete $(\mathrm{\ell },q\mathrm{/}{\mathrm{\ell }}^2)$-blockade, then $q\mathrm{/}{\mathrm{\ell }}^2\ge ϵm\cdot {ϵ}^4={ϵ}^{5}m=y^{a(c_1+5)}\mathrm{\mid }G\mathrm{\mid }\ge y^{a_3}\mathrm{\mid }G\mathrm{\mid }$, because $\mathrm{\ell }=\lceil {ϵ}^{-1}\rceil \le {ϵ}^{-2}$ for $ϵ\in (0,\frac{1}{2})$ and step 1.1 has $a_3\ge a(c_1+5)$. Since also $\mathrm{\ell }\ge {ϵ}^{-1}=y^{-a}\ge y^{-1}$, outcome 3 follows.

We may therefore assume [L6] yields anticonnected subsets $B_i\subseteq D_i$ of common size $w:=\lceil q\mathrm{/}\mathrm{\ell }\rceil$ such that every distinct pair is either complete or mutually $({ϵ}^{c_2-5}\mathrm{\ell })$-sparse. Because $\mathrm{\ell }\le {ϵ}^{-2}$, every noncomplete pair is in fact mutually ${ϵ}^{c_2-7}$-sparse. Also $w\ge q\mathrm{/}\mathrm{\ell }\ge {ϵ}^{3}m={ϵ}^{c_1+3}\mathrm{\mid }G\mathrm{\mid }=y^{a(c_1+3)}\mathrm{\mid }G\mathrm{\mid }\ge y^{a_3}\mathrm{\mid }G\mathrm{\mid }$, since $q\ge ϵm$ and $\mathrm{\ell }\le {ϵ}^{-2}$. Since step 2.1 fails, $\mathrm{\mid }G\mathrm{\mid }>y^{-a_3}$, and because $a_3\ge a(c_1+5)$ with $ϵ=y^a$, this gives $m={ϵ}^{c_1}\mathrm{\mid }G\mathrm{\mid }>y^{-5a}={ϵ}^{-5}$ and hence $q=\lceil ϵ\lceil m\rceil \rceil >ϵm>{ϵ}^{-4}\ge {ϵ}^{-2}\ge \mathrm{\ell }$. Therefore $\mathrm{\mid }V(\mathcal{B})\mathrm{\mid }={\sum }_{i=1}^{\mathrm{\ell }}\mathrm{\mid }{B}_i\mathrm{\mid }\le \mathrm{\ell }(q\mathrm{/}\mathrm{\ell }+1)=q+\mathrm{\ell }\le 2q\le 2\lceil m\rceil \le 4m\le {ϵ}^{c_1-2}\mathrm{\mid }G\mathrm{\mid }\le ϵ\mathrm{\mid }G\mathrm{\mid }\le y\mathrm{\mid }G\mathrm{\mid }$, where $\mathcal{B}:=(B_1,\dots ,B_{\mathrm{\ell }})$. Since $c_2\ge 8$, one has ${ϵ}^{c_2-7}=y^{a(c_2-7)}\le y^a$. Therefore the hypotheses of [L7] hold for $\mathcal{B}$.

Applying [L7] to $\mathcal{B}$ yields either a $y^4$-restricted induced subgraph of size at least $w$, giving outcome 2, or disjoint sets $X,Y\subseteq V(G)$ with $\mathrm{\mid }X\mathrm{\mid }=w\ge y^{a_3}\mathrm{\mid }G\mathrm{\mid }$, $\mathrm{\mid }Y\mathrm{\mid }\ge (1-4y)\mathrm{\mid }G\mathrm{\mid }\ge (1-a_{5}y)\mathrm{\mid }G\mathrm{\mid }$, and $Y$ anticomplete to $X$, giving outcome 4.

The cases in steps 2.1, 2.2, 2.3, and 5.1 exhaust all possibilities, so one of the four stated outcomes always holds.

Let $n$ be maximal such that $G$ has a blockade $(B_1,\dots ,B_n)$ with $\mathrm{\mid }{B}_i\mathrm{\mid }\ge y^{a+2}\mathrm{\mid }G\mathrm{\mid }$ for all $i\in [n]$, with $\mathrm{\mid }{B}_n\mathrm{\mid }\ge (1-by{)}^n\mathrm{\mid }G\mathrm{\mid }$, and with the property that for each $i\in [n]$, either every later block is complete to $B_i$, or every later block is anticomplete to $B_i$. This is possible because $0<y^{a+2}\le 1$, so $B_1:=V(G)$ already satisfies the required lower bounds.

Suppose $n<2y^{-1}$. The bound $y\le c=2^{-4b}$ implies $by<\frac{1}{2}$, and the elementary inequality $1-t\ge 2^{-2t}$ for $t\in [0,\frac{1}{2}]$ gives $(1-by{)}^n\ge (1-by{)}^{2y^{-1}}\ge 2^{-4b}=c$. Hence $\mathrm{\mid }{B}_n\mathrm{\mid }\ge c\mathrm{\mid }G\mathrm{\mid }$, so the hypothesis applies to $G[B_n]$. Choose disjoint $X,Y\subseteq B_n$ with $\mathrm{\mid }X\mathrm{\mid }\ge y^a\mathrm{\mid }{B}_n\mathrm{\mid }\ge y^{a}c\mathrm{\mid }G\mathrm{\mid }\ge y^{a+2}\mathrm{\mid }G\mathrm{\mid },$ where the last inequality uses $c\ge y\ge y^2$, and with $\mathrm{\mid }Y\mathrm{\mid }\ge (1-by)\mathrm{\mid }{B}_n\mathrm{\mid }\ge (1-by{)}^{n+1}\mathrm{\mid }G\mathrm{\mid }$, and $Y$ complete or anticomplete to $X$. Moreover, $\mathrm{\mid }Y\mathrm{\mid }\ge (1-by)c\mathrm{\mid }G\mathrm{\mid }>\frac{1}{2}c\mathrm{\mid }G\mathrm{\mid }\ge \frac{1}{2}y\mathrm{\mid }G\mathrm{\mid }\ge y^{a+2}\mathrm{\mid }G\mathrm{\mid },$ where the last inequality follows from $a>1$ and $y\le \frac{1}{2}$. Because $X\cup Y\subseteq B_n$, every earlier block has the same pure relation to both $X$ and $Y$ that it had to $B_n$. Thus $(B_1,\dots ,B_{n-1},X,Y)$ is a longer blockade of the same type, contradicting the maximality of $n$. So $n\ge 2y^{-1}$.

Let $Q$ be the set of indices $i$ such that every later block is complete to $B_i$, and let $R$ be the set of indices $i$ such that every later block is anticomplete to $B_i$. By construction every index lies in $Q\cup R$, so one of $Q$ or $R$ has size at least $n\mathrm{/}2\ge y^{-1}$.

If $\mathrm{\mid }Q\mathrm{\mid }\ge y^{-1}$, choose $\lceil y^{-1}\rceil$ indices from $Q$ in their inherited order. The corresponding blocks form a complete blockade, and every block has size at least $y^{a+2}\mathrm{\mid }G\mathrm{\mid }$ by step 1.1. If instead $\mathrm{\mid }R\mathrm{\mid }\ge y^{-1}$, the same construction with $R$ gives an anticomplete blockade. In either case we obtain a complete or anticomplete $(\lceil y^{-1}\rceil ,y^{a+2}\mathrm{\mid }G\mathrm{\mid })$-blockade.

Therefore the stated blockade exists.

Let $a_1,a_2,a_5,a_3,a_4$ be as in [L1], and set $c:=\min \{2^{-4a_5},(2a_5{)}^{-1},1\mathrm{/}4\}$, $c_1:=a_1+1$, $c_2:=a_2$, $c_3:=a_3+2$, and $c_4:=a_4$. Then $c\in (0,\frac{1}{2})$ and $c_3\ge c_4\ge 4$.

If $\mathrm{\mid }G\mathrm{\mid }\le y^{-c_3}$, then any one-vertex induced subgraph of $G$ is $y^{c_4}$-restricted and has size at least $y^{c_3}\mathrm{\mid }G\mathrm{\mid }$, so outcome 3 holds.

Suppose every induced subgraph $F$ of $G$ with $\mathrm{\mid }F\mathrm{\mid }\ge c\mathrm{\mid }G\mathrm{\mid }$ contains disjoint sets $X,Y\subseteq V(F)$ with $\mathrm{\mid }X\mathrm{\mid }\ge y^{a_3}\mathrm{\mid }F\mathrm{\mid }$, $\mathrm{\mid }Y\mathrm{\mid }\ge (1-a_{5}y)\mathrm{\mid }F\mathrm{\mid }$, and $Y$ complete or anticomplete to $X$. Since $y\le c\le (2a_5{)}^{-1}$ and $c\le 2^{-4a_5}$, the hypotheses of [L2] are satisfied with $a=a_3$ and $b=a_5$. Therefore [L2] yields a complete or anticomplete $(\lceil y^{-1}\rceil ,y^{a_3+2}\mathrm{\mid }G\mathrm{\mid })$-blockade in $G$. Because $c_3=a_3+2$ and $1\mathrm{/}\lceil y^{-1}\rceil \le y$, each block has size at least $y^{c_3}\mathrm{\mid }G\mathrm{\mid }\ge \mathrm{\mid }G\mathrm{\mid }\mathrm{/}\lceil y^{-1}{\rceil }^{c_3}$. Hence outcome 2 holds after shrinking to exactly $\lceil y^{-1}\rceil$ blocks if necessary.

We may therefore choose an induced subgraph $F$ of $G$ with $\mathrm{\mid }F\mathrm{\mid }\ge c\mathrm{\mid }G\mathrm{\mid }$ for which no such almost-pure pair exists. Because $G$ is $cy$-restricted and $\mathrm{\mid }F\mathrm{\mid }\ge c\mathrm{\mid }G\mathrm{\mid }$, [L3] implies that $F$ is $y$-restricted. Apply [L1] to $F$. Its fourth outcome is excluded by the choice of $F$. If [L1] gives a clique or stable set of size at least $(y^{a_1}\mathrm{\mid }F\mathrm{\mid }{)}^{a_2}$, then $(y^{a_1}\mathrm{\mid }F\mathrm{\mid }{)}^{a_2}\ge (y^{a_1+1}\mathrm{\mid }G\mathrm{\mid }{)}^{a_2}=(y^{c_1}\mathrm{\mid }G\mathrm{\mid }{)}^{c_2}$, because $\mathrm{\mid }F\mathrm{\mid }\ge c\mathrm{\mid }G\mathrm{\mid }\ge y\mathrm{\mid }G\mathrm{\mid }$. So outcome 1 holds. If [L1] gives a complete or anticomplete blockade $(k,\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^{a_3})$ with $k\ge y^{-1}$, then $\mathrm{\mid }F\mathrm{\mid }\mathrm{/}{k}^{a_3}\ge c\mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{a_3}\ge y^2\mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{a_3}\ge \mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{a_3+2}=\mathrm{\mid }G\mathrm{\mid }\mathrm{/}{k}^{c_3}$, because $c\ge y\ge y^2$ and $y\ge 1\mathrm{/}k$. So outcome 2 holds. Finally, if [L1] gives a $y^{a_4}$-restricted induced subgraph of size at least $y^{a_3}\mathrm{\mid }F\mathrm{\mid }$, then $y^{a_3}\mathrm{\mid }F\mathrm{\mid }\ge y^{a_3}c\mathrm{\mid }G\mathrm{\mid }\ge y^{a_3+2}\mathrm{\mid }G\mathrm{\mid }=y^{c_3}\mathrm{\mid }G\mathrm{\mid }$, because $c\ge y^2$, and $a_4=c_4$. So outcome 3 holds.

Steps 2.1, 2.2, and 2.3 cover all cases, so one of the three stated outcomes always holds.

By hypothesis 1, there exists at least one induced subgraph of $G$ that is $c$-restricted and has at least $c^{b_2}\mathrm{\mid }G\mathrm{\mid }$ vertices. Therefore the set of admissible restriction parameters considered below is nonempty.

For a nonempty induced subgraph $E$ of $G$, let $\rho (E)$ be the smallest real number $\lambda \in [0,1]$ such that $E$ is $\lambda$-restricted. Because $E$ is finite, [L1] shows that $\rho (E)$ is attained by one of finitely many degree or codegree ratios in $E$. Choose an induced subgraph $F$ of $G$ for which $\lambda :=\max (x^{b_1},\rho (F))$ is minimal subject to $\mathrm{\mid }F\mathrm{\mid }\ge {\lambda }^{b_2}\mathrm{\mid }G\mathrm{\mid }$. Step 1.1 ensures that such a choice exists and that $\lambda \le c$.

Suppose $\lambda \ge x$. Then $\lambda =\rho (F)$, so hypothesis 2 applies to $F$ and yields a ${\lambda }^{b_1}$-restricted induced subgraph $F^{\mathrm{\prime }}\subseteq F$ with $\mathrm{\mid }{F}^{\mathrm{\prime }}\mathrm{\mid }\ge {\lambda }^{b_3}\mathrm{\mid }F\mathrm{\mid }\ge {\lambda }^{b_2+b_3}\mathrm{\mid }G\mathrm{\mid }\ge {\lambda }^{b_1{b}_2}\mathrm{\mid }G\mathrm{\mid }$, where the last inequality uses $b_1{b}_2\ge b_2+b_3$. Because $F^{\mathrm{\prime }}$ is ${\lambda }^{b_1}$-restricted, its admissible parameter satisfies $\max (x^{b_1},\rho (F^{\mathrm{\prime }}))\le {\lambda }^{b_1}<\lambda$, while $\mathrm{\mid }{F}^{\mathrm{\prime }}\mathrm{\mid }\ge \max (x^{b_1},\rho (F^{\mathrm{\prime }}){)}^{b_2}\mathrm{\mid }G\mathrm{\mid }$. This contradicts the minimal choice of $\lambda$ in step 2.1. Hence $\lambda <x$.

Since $\lambda =\max (x^{b_1},\rho (F))$, step 2.1 gives $x^{b_1}\le \lambda <x$ by step 3.1. Therefore $\rho (F)\le \lambda <x$, so $F$ is $x$-restricted. Its size also satisfies $\mathrm{\mid }F\mathrm{\mid }\ge {\lambda }^{b_2}\mathrm{\mid }G\mathrm{\mid }\ge (x^{b_1}{)}^{b_2}\mathrm{\mid }G\mathrm{\mid }=x^{b_1{b}_2}\mathrm{\mid }G\mathrm{\mid }$.