A sparse graph either sparsifies further or yields a comb or a large sparse pair

[assume-case pair] If outcome 1 already holds, there is nothing to prove.

[assume-case sparser] If outcome 2 already holds, there is nothing to prove.

[assume-case comb] Assume now that outcomes 1 and 2 both fail. Then [L1] gives a vertex $v\in V(G)$ and disjoint sets $A,B\subseteq V(G)\setminus \{v\}$ with $A\subseteq V(G)\setminus N_G[v]$, $B\subseteq N_G(v)$, and the displayed nearly covered sparse pair properties. In particular $A$ and $B$ are nonempty.

Apply [L2] with $\xi =x^2$ to the sets $A,B$. We obtain a set $S\subseteq A$ with $\mathrm{\mid }S\mathrm{\mid }\le \lceil x^{-2}\rceil$ such that at least half of the vertices of $B$ have a neighbour in $S$. Let $B^{\mathrm{\prime }}\subseteq B$ be the set of vertices with a neighbour in $S$; then $\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}2\ge \frac{1}{2}{y}^4\mathrm{\mid }V(G)\mathrm{\mid }$.

Consider the bipartite graph between $S$ and $B^{\mathrm{\prime }}$. Every vertex of $B^{\mathrm{\prime }}$ has a neighbour in $S$ by definition. Since $A$ is $y^2$-sparse to $B$ and $S\subseteq A$, every vertex of $S$ has at most $y^2\mathrm{\mid }B\mathrm{\mid }$ neighbours in $B^{\mathrm{\prime }}$. Apply [L3] with $d:=1\mathrm{/}2$, $\mathrm{\Delta }:=y^2\mathrm{\mid }B\mathrm{\mid }$, and $\mathrm{\Gamma }:=\mathrm{\mid }B\mathrm{\mid }$.

The second alternative of [L3] is impossible for these parameters, because it would give $\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\le \frac{3^{3\mathrm{/}2}}{3\mathrm{/}2-\sqrt{3\mathrm{/}2}}\mathrm{\mid }B{\mathrm{\mid }}^{1\mathrm{/}2}(y^2\mathrm{\mid }B\mathrm{\mid }{)}^{1\mathrm{/}2}=\frac{3^{3\mathrm{/}2}}{3\mathrm{/}2-\sqrt{3\mathrm{/}2}}y\mathrm{\mid }B\mathrm{\mid }$. The constant in front of $y\mathrm{\mid }B\mathrm{\mid }$ is less than $20$, while $\mathrm{\mid }{B}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}2>20y\mathrm{\mid }B\mathrm{\mid }$ since $y\le 2^{-8}<1\mathrm{/}40$. Hence [L3] yields a $(\mathrm{\ell },\mathrm{\mid }B\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2)$-comb $((a_i,B_i):i\in [\mathrm{\ell }])$ with each $a_i\in S$ and each $B_i\subseteq B^{\mathrm{\prime }}$.

Because the teeth $a_i$ are distinct members of $S$, we have $\mathrm{\ell }\le \mathrm{\mid }S\mathrm{\mid }\le \lceil x^{-2}\rceil$. Also [L4] gives $\mathrm{\mid }{B}_i\mathrm{\mid }\ge \mathrm{\mid }B\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2$ for each tooth block, while every $a_i\in S\subseteq A$ has at most $y^2\mathrm{\mid }B\mathrm{\mid }$ neighbours in $B$. Since $a_i$ is complete to $B_i$ by [L4], this forces $\mathrm{\mid }B\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2\le \mathrm{\mid }{B}_i\mathrm{\mid }\le y^2\mathrm{\mid }B\mathrm{\mid }$, and therefore $\mathrm{\ell }\ge y^{-1}$. Finally $\mathrm{\mid }B\mathrm{\mid }\ge y^4\mathrm{\mid }V(G)\mathrm{\mid }$ from step 1.3, so each block has size at least $y^4\mathrm{\mid }V(G)\mathrm{\mid }\mathrm{/}{\mathrm{\ell }}^2$.

By step 1.3, we already have a vertex $v$ with $B\subseteq N_G(v)$ and $A\subseteq V(G)\setminus N_G[v]$. Since each $a_i\in A$ and each $B_i\subseteq B$, the vertex $v$ is complete to ${\bigcup }_i{B}_i$ and anticomplete to $\{a_i:i\in [\mathrm{\ell }]\}$. Together with step 5.1, this is exactly outcome 3.

The three cases 1.1, 1.2, and 1.3 exhaust the possibilities, so one of the stated outcomes always holds.