Pure Pairs, Forests and Path–Antipath Classes

By [L1], if $G$ is disconnected then the first alternative of the Statement already holds. Assume instead that $G$ is connected.

Suppose for contradiction that $G$ is also anticonnected. Then [L2] makes $\bar{G}$ connected. Choose a vertex $v\in V(G)$. Because $G$ is connected and nontrivial, [F1] gives a neighbour $x$ of $v$. Because $\bar{G}$ is connected, [F1] also gives a vertex $y$ nonadjacent to $v$. Among all pairs $(a,b)$ with $va\in E(G)$ and $vb\mathrm{\notin }E(G)$, choose one for which the distance from $a$ to $b$ in $G$ is minimal. Let $a=u_0,u_1,\dots ,u_m=b$ be a shortest $a$-$b$ path in $G$.

Since $a$ and $b$ are nonadjacent, one has $m\ge 2$. A shortest path is induced, so $u_0{u}_2\mathrm{\notin }E(G)$ and no nonconsecutive pair among $u_0,u_1,\dots ,u_m$ is adjacent. If some $u_i$ with $1\le i<m$ were adjacent to $v$, then $(u_i,b)$ would be another neighbour/nonneighbour pair for $v$ whose distance is $m-i<m$, contradicting the choice in step 2.1. Hence $v{u}_1,v{u}_2\mathrm{\notin }E(G)$.

The four vertices $v,u_0,u_1,u_2$ therefore induce a path: the edges are $v{u}_0$, $u_0{u}_1$, and $u_1{u}_2$, while the nonedges are $v{u}_1$, $v{u}_2$, and $u_0{u}_2$. This is an induced copy of $P_4$, contradicting [L3].

So a nontrivial $P_4$-free graph cannot be both connected and anticonnected. Since step 1.1 reduced to the connected case, [L2] shows that whenever $G$ is connected, $\bar{G}$ must be disconnected.

We prove by induction on $n$ the stronger statement $\alpha (G)\omega (G)\ge n$. If $n\le 1$, then $\alpha (G)=1$ when $n=1$ and $\alpha (G)=\omega (G)=0$ when $n=0$, so the inequality is immediate.

Assume $n\ge 2$. By [L2], either $G$ is disconnected or $\bar{G}$ is disconnected.

Suppose first that $G$ is disconnected. By [L3], choose a connected component $C$ of $G$ and let $D:=V(G)\setminus C$; then $C$ and $D$ are nonempty, $G[C]$ and $G[D]$ are induced subgraphs of $G$, and [L4] makes $C$ anticomplete to $D$. By [L1] both induced subgraphs are $P_4$-free, so the induction hypothesis gives $\alpha (G[C])\omega (G[C])\ge \mathrm{\mid }C\mathrm{\mid }$ and $\alpha (G[D])\omega (G[D])\ge \mathrm{\mid }D\mathrm{\mid }$. A stable set in $G[C]$ together with a stable set in $G[D]$ is still stable in $G$, while every clique of $G$ lies in one side. Hence $\alpha (G)\ge \alpha (G[C])+\alpha (G[D])$ and $\omega (G)\ge \max \{\omega (G[C]),\omega (G[D])\}$, so $\alpha (G)\omega (G)\ge \alpha (G[C])\omega (G[C])+\alpha (G[D])\omega (G[D])\ge \mathrm{\mid }C\mathrm{\mid }+\mathrm{\mid }D\mathrm{\mid }=n$.

Suppose instead that $\bar{G}$ is disconnected. By [L3], choose an anticomponent $C$ of $G$ and let $D:=V(G)\setminus C$; then $C$ and $D$ are nonempty, the induced subgraphs $G[C]$ and $G[D]$ are $P_4$-free by [L1], and [L4] makes $C$ complete to $D$. The induction hypothesis again yields $\alpha (G[C])\omega (G[C])\ge \mathrm{\mid }C\mathrm{\mid }$ and $\alpha (G[D])\omega (G[D])\ge \mathrm{\mid }D\mathrm{\mid }$. Now a clique in $G[C]$ together with a clique in $G[D]$ is a clique in $G$, while every stable set of $G$ lies in one side. Thus $\omega (G)\ge \omega (G[C])+\omega (G[D])$ and $\alpha (G)\ge \max \{\alpha (G[C]),\alpha (G[D])\}$, and again $\alpha (G)\omega (G)\ge \mathrm{\mid }C\mathrm{\mid }+\mathrm{\mid }D\mathrm{\mid }=n$.

Steps 3.1 and 3.2 prove $\alpha (G)\omega (G)\ge n$. Since $\max \{\alpha (G),\omega (G){\}}^2\ge \alpha (G)\omega (G)$, one obtains $\max \{\alpha (G),\omega (G)\}\ge \sqrt{n}$. By [L5], this says that $G$ has a clique or a stable set of size at least $\sqrt{n}$.

If every nonempty graph in $\mathcal{C}$ has one vertex, then $1$ is already an Erdős–Hajnal constant, so there is nothing to prove. We therefore assume that $\mathcal{C}$ contains some graph with at least two vertices. Let $\eta >0$ be the strong Erdős–Hajnal constant from [L1]. Applying [L1] to one nontrivial graph in $\mathcal{C}$ gives disjoint sets $A$ and $B$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \eta \mathrm{\mid }V(G)\mathrm{\mid }$, hence $2\eta \le 1$. Choose $c>0$ so that $2{\eta }^c=1$.

We claim that every nonempty graph $G\in \mathcal{C}$ induces a $P_4$-free subgraph on at least $\mathrm{\mid }V(G){\mathrm{\mid }}^c$ vertices. We prove this by induction on $\mathrm{\mid }V(G)\mathrm{\mid }$, and the case $\mathrm{\mid }V(G)\mathrm{\mid }=1$ is immediate.

Let $G\in \mathcal{C}$ with $n:=\mathrm{\mid }V(G)\mathrm{\mid }\ge 2$, and assume the claim for smaller orders. By [L1], choose disjoint sets $A,B\subseteq V(G)$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \eta n$ and $(A,B)$ pure. By [L2], the induced subgraphs $G[A]$ and $G[B]$ both lie in $\mathcal{C}$, so the induction hypothesis gives induced $P_4$-free subgraphs $H_A\subseteq G[A]$ and $H_B\subseteq G[B]$ with $\mathrm{\mid }V(H_A)\mathrm{\mid }\ge \mathrm{\mid }A{\mathrm{\mid }}^c$ and $\mathrm{\mid }V(H_B)\mathrm{\mid }\ge \mathrm{\mid }B{\mathrm{\mid }}^c$.

Let $H:=G[V(H_A)\cup V(H_B)]$. The pair $(V(H_A),V(H_B))$ is still pure because it sits inside the pure pair $(A,B)$. No induced $P_4$ can lie entirely in one side, since $H_A$ and $H_B$ are each $P_4$-free. A $1+3$ split is impossible because the lone vertex would be complete or anticomplete to the three opposite vertices, while a vertex of $P_4$ is neither complete nor anticomplete to the other three. A $2+2$ split is impossible as well: a complete cross-pair gives four cross edges, and an anticomplete cross-pair gives none, whereas $P_4$ has exactly three edges and is connected. Hence $H$ is $P_4$-free.

By [L5], $\mathrm{\mid }V(H)\mathrm{\mid }=\mathrm{\mid }V(H_A)\mathrm{\mid }+\mathrm{\mid }V(H_B)\mathrm{\mid }\ge \mathrm{\mid }A{\mathrm{\mid }}^c+\mathrm{\mid }B{\mathrm{\mid }}^c\ge 2(\eta n{)}^c=2{\eta }^c{n}^c=n^c$. This closes the induction and proves the claim from step 2.1.

Let $G$ be any nonempty graph in $\mathcal{C}$. By step 5.1, $G$ contains an induced $P_4$-free subgraph $H$ with $\mathrm{\mid }V(H)\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^c$. Then [L3] gives a clique or stable set in $H$ of size at least $\mathrm{\mid }V(H){\mathrm{\mid }}^{1\mathrm{/}2}\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{c\mathrm{/}2}$, and the same set is a clique or stable set in $G$. By [L4], the exponent $c\mathrm{/}2$ is an Erdős–Hajnal constant for $\mathcal{C}$.

By [F1], choose ${\delta }_H>0$ and disjoint sets $A,B\subseteq V(G)$ with $\mathrm{\mid }A\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{{\delta }_H},\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }V(G){\mathrm{\mid }}^{{\delta }_H},$ such that $A$ is complete or anticomplete to $B$. Set $c_H:={\delta }_H$. Then $\mathrm{\mid }A\mathrm{\mid }$ and $\mathrm{\mid }B\mathrm{\mid }$ are certainly at least $\lfloor \mathrm{\mid }V(G){\mathrm{\mid }}^{c_H}\rfloor$.

By [L1], the pair $(A,B)$ is pure. Therefore the constant $c_H$ has the required property.

We first prove the connected-case claim: for each $r\ge 2$ there are constants ${\epsilon }_r>0$ and $c_r>0$ such that every connected graph $J$ on $m\ge 2$ vertices has a vertex of degree greater than ${\epsilon }_{r}m$, or contains an induced $P_r$ starting at every vertex, or has a biclique of size at least $c_{r}m$ in $\bar{J}$. We prove this by induction on $r$.

For $r=2$, choose ${\epsilon }_2:=1\mathrm{/}2$ and $c_2:=1\mathrm{/}4$. Every vertex of a connected graph on at least two vertices is incident with an edge, so every vertex starts an induced $P_2$. Thus the claim holds for $r=2$.

Fix $r>2$, assume the claim for $r-1$, and let ${\epsilon }_r:={\epsilon }_{r-1}\mathrm{/}(2+{\epsilon }_{r-1})$. Since ${\epsilon }_r<1\mathrm{/}2$, choose any constant $0<c_r\le \min \{(1-2{\epsilon }_r)\mathrm{/}4,c_{r-1}(1-{\epsilon }_r)\mathrm{/}2\}$. Now let $J$ be a connected graph on $m\ge 2$ vertices for which the first outcome fails, so every vertex has degree at most ${\epsilon }_{r}m$. Fix a vertex $v_1$ and put $S:=V(J)\setminus (N_J(v_1)\cup \{v_1\})$. Then $\mathrm{\mid }S\mathrm{\mid }\ge (1-{\epsilon }_r)m-1$. Since $J$ is connected, $v_1$ has degree at least $1$, so $m\ge 1\mathrm{/}{\epsilon }_r$ and therefore $\mathrm{\mid }S\mathrm{\mid }\ge (1-2{\epsilon }_r)m$.

Suppose every connected component of $J[S]$ has size at most $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Choose components greedily until their union $A$ has size in the interval $[\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4,\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2]$: if the running union first reaches $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4$ before it exceeds $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$, stop there; otherwise the next component itself has size in $[\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4,\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2]$ and we take that one alone. Let $B:=S\setminus A$. Then $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }S\mathrm{\mid }\mathrm{/}4$, and [L3] makes $A$ anticomplete to $B$ in $J$. Hence $A$ and $B$ form a biclique of size at least $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}4\ge c_{r}m$ in $\bar{J}$.

Suppose instead that $J[S]$ has a connected component $S^{\mathrm{\prime }}$ with $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Because $J$ is connected, some vertex $v_2\in N_J(v_1)$ has a neighbour in $S^{\mathrm{\prime }}$. Let $J_2:=J[S^{\mathrm{\prime }}\cup \{v_2\}]$, which is connected. Every vertex of $J_2$ still has degree at most ${\epsilon }_{r}m$, and ${\epsilon }_{r}m={\epsilon }_{r-1}(1-{\epsilon }_r)m\mathrm{/}2<{\epsilon }_{r-1}(\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }+1)={\epsilon }_{r-1}\mathrm{\mid }V(J_2)\mathrm{\mid }$ because $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }+1>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2+1\ge (1-{\epsilon }_r)m\mathrm{/}2$. So the first outcome of the induction hypothesis is false for $J_2$.

Apply the induction hypothesis to $J_2$ with parameter $r-1$. If outcome 2 holds there, then $J_2$ contains an induced $P_{r-1}$ starting at $v_2$, and prefixing this path with $v_1$ gives an induced $P_r$ in $J$ starting at $v_1$ because $v_1$ is adjacent to $v_2$ and has no neighbours in $S^{\mathrm{\prime }}$. If outcome 3 holds there, then $\overline{J_2}$ contains a biclique of size at least $c_{r-1}\mathrm{\mid }V(J_2)\mathrm{\mid }\ge c_{r-1}(1-{\epsilon }_r)m\mathrm{/}2\ge c_{r}m$, and the same biclique lies in $\bar{J}$. Thus, whenever outcome 1 fails for $J$, either outcome 2 or outcome 3 follows. This completes the induction and proves the connected-case claim.

Let $\epsilon :={\epsilon }_k\mathrm{/}8$. Because $P_k$ is the standard $k$-vertex path, [L1] applied to $H=P_k$ yields a constant $\delta >0$ such that every nonempty $P_k$-free graph has a vertex set of size at least $\delta n$ whose self-density is at most $\epsilon$ or at least $1-\epsilon$.

Let $G$ be a graph with no induced $P_k$ and no induced $\overline{P_k}$, and let $n:=\mathrm{\mid }V(G)\mathrm{\mid }\ge 2$. If $G$ has a set of size at least $\delta n$ and self-density at least $1-\epsilon$, apply the same argument to $\bar{G}$: an induced $P_k$ in $\bar{G}$ would be an induced $\overline{P_k}$ in $G$, and an induced $\overline{P_k}$ in $\bar{G}$ would be an induced $P_k$ in $G$. So $\bar{G}$ belongs to the same forbidden class. Replacing $G$ by $\bar{G}$ if necessary, we may assume that $G$ has a set $S_0$ with $\mathrm{\mid }{S}_0\mathrm{\mid }\ge \delta n$ and self-density at most $\epsilon$.

By [L2], the set $S_0$ contains a subset $S$ with $\mathrm{\mid }S\mathrm{\mid }\ge \mathrm{\mid }{S}_0\mathrm{\mid }\mathrm{/}2\ge \delta n\mathrm{/}2$ such that $S$ is $4\epsilon$-sparse. By [F1], every vertex of $G[S]$ therefore has degree at most $4\epsilon \mathrm{\mid }S\mathrm{\mid }={\epsilon }_k\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$.

If every connected component of $G[S]$ has size at most $\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$, then the same greedy argument as in step 4.1 partitions those components into anticomplete sets $A,B\subseteq S$ with $\mathrm{\mid }A\mathrm{\mid },\mathrm{\mid }B\mathrm{\mid }\ge \mathrm{\mid }S\mathrm{\mid }\mathrm{/}4\ge \delta n\mathrm{/}8$. This is already a pure pair in $G$.

Otherwise $G[S]$ has a connected component $S^{\mathrm{\prime }}$ with $\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }>\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2$. Every vertex of $G[S^{\mathrm{\prime }}]$ has degree at most ${\epsilon }_k\mathrm{\mid }S\mathrm{\mid }\mathrm{/}2<{\epsilon }_k\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }$, and $G[S^{\mathrm{\prime }}]$ is $P_k$-free because induced subgraphs preserve forbidden induced paths. Applying the connected-case claim from step 5.1 to the connected graph $G[S^{\mathrm{\prime }}]$, outcome 1 is false by the degree bound and outcome 2 is false because $G[S^{\mathrm{\prime }}]$ contains no induced $P_k$ at all. Hence outcome 3 holds, so $\overline{G[S^{\mathrm{\prime }}]}$ has a biclique with both sides of size at least $c_k\mathrm{\mid }{S}^{\mathrm{\prime }}\mathrm{\mid }\ge c_k\delta n\mathrm{/}4$. Equivalently, $G$ has an anticomplete pair of that size.

Let ${\gamma }_k:=\min \{\delta \mathrm{/}8,c_k\delta \mathrm{/}4\}$. Steps 9.1 and 9.2 show that every graph with no induced $P_k$ or $\overline{P_k}$ and at least two vertices contains a pure pair with both sides of size at least ${\gamma }_{k}n$. By [L4], the class forbidding $P_k$ and $\overline{P_k}$ has the strong Erdős–Hajnal property.

The previous theorem gives the strong Erdős–Hajnal property for the hereditary class of graphs forbidding $P_k$ and $\overline{P_k}$.

Applying [L2] to that class yields the Erdős–Hajnal property.

List the finitely many ordered trees on at most $\tau$ vertices. By repeated application of [L1], one tree at a time, choose $K$ large enough that every $K$-block blockade has a $k$-block sub-blockade whose trace is monochromatic for every tree on this list. This is a backward iteration of finitely many finite Ramsey numbers; when an order has fewer than $s$ blocks, its $s$-vertex trace is empty.

For this $K$, there are at most ${\tau }^{\tau }$ ordered-tree types on at most $\tau$ vertices: root each tree at its first ordered vertex; for size $s$ the parent map on the other $s-1$ ordered positions has at most $s^{s-1}$ possibilities, and ${\sum }_{s=1}^{\tau }{s}^{s-1}\le {\tau }^{\tau }$. Each trace has at most $2^K$ supports. Thus the sum $c_{\tau }$ of all trace cardinalities is an integer in $[0,M]$, where $M=2^K{\tau }^{\tau }$.

Start by trimming all blocks to width $W$. Choose the largest integer $t\in [0,M]$ for which an equicardinal contraction $\mathcal{C}$ of the original $K$-block blockade has width at least ${\kappa }^{t}W$ and $c_{\tau }(\mathcal{C})\le M-t$. Such a $t$ exists because $t=0$ works. If $\mathcal{C}$ were not $(\kappa ,\tau )$-support-invariant, some contraction of it of width at least $\kappa \mathrm{width}(\mathcal{C})$ would remove a support from the trace of an ordered tree of size at most $\tau$. Trim its blocks to equal size. Trimming can only remove further supports, so the new equicardinal contraction has width at least ${\kappa }^{t+1}W$ and cost at most $M-t-1$. This contradicts maximality of $t$. Hence $\mathcal{C}$ is invariant and has width at least ${\kappa }^{M}W$.

Apply the Ramsey choice of step 1.1 to $\mathcal{C}$: for each ordered tree $J$ of size $s\le \tau$, color every $s$-subset of block indices by whether it belongs to its trace, and successively retain a monochromatic sub-blockade. Keep exactly $k$ blocks. Each trace is empty or contains every $s$-subset, so this minor is $\tau$-support-uniform.

Support-invariance survives taking a sub-blockade: extend any contraction of the sub-blockade to the discarded blocks unchanged; since all original blocks of $\mathcal{C}$ have the same size, the extended contraction retains at least the same $\kappa$ fraction of its width. A copy on retained indices survives in the extended contraction if and only if it survives in the restricted one. Thus the sub-blockade is also $(\kappa ,\tau )$-support-invariant, equicardinal, and retains the width lower bound from step 2.1.

Let $\alpha$ and $\beta$ be the greatest heights of a $\mathcal{B}$-left-rainbow and a $\mathcal{B}$-right-rainbow rooted complete $\delta$-ary tree, respectively. The single vertex gives both a starting value, and settles the case $\eta =0$. Suppose $\eta \ge 1$ and there is no rainbow $T(\delta ,\eta )$. Then $\alpha ,\beta <\eta$; reverse the blockade if needed so that $\alpha \le \beta$. For $0\le q\le \delta$, define $Q(q)$ by joining a new root to the roots of $q$ disjoint copies of $T(\delta ,\alpha )$. Put $R(q)=Q(q)$ for $q\le \delta$; for $q=\delta +i$, $1\le i\le \delta$, use $\delta -i$ copies of $T(\delta ,\alpha )$ and $i$ copies of $T(\delta ,\beta )$ instead. Let $S(q)$, $0\le q\le \delta$, consist of $q+1$ copies of $T(\delta ,\alpha )$ with the root of the first joined to the other $q$ roots and retained as root. Let ${\gamma }_3$ be maximal such that a left-rainbow $S({\gamma }_3)$ occurs. Such a copy exists at $q=0$. Because $Q(\delta )=T(\delta ,\alpha +1)$, $R(2\delta )=T(\delta ,\beta +1)$ and $S(\delta )$ contains a rooted $T(\delta ,\alpha +1)$, none of these three extremal cases can occur.

Call a minor $(C_1,\dots ,C_k,C_K)$, with $C_i\subseteq B_i$, $({\gamma }_1,{\gamma }_2)$-anchored if some $Y\subseteq B_{k+1}\cup \cdots \cup B_{K-1}$ is anticomplete to $C_2,\dots ,C_k$, every $v\in C_1$ roots a left-rainbow $Q({\gamma }_1)$ inside $Y\cup \{v\}$, and every $v\in C_K$ roots a right-rainbow $R({\gamma }_2)$ there. The original blockade, with $k=K-1$, $Y=\mathrm{\varnothing }$ and ${\gamma }_1={\gamma }_2=0$, is anchored. Choose ${\gamma }_0={\gamma }_1+{\gamma }_2$ maximal among anchored minors of length at least $K-2{\delta }^{\eta +1}{\gamma }_0$ and width at least $W{2}^{-3{\gamma }_0}$; trim its blocks equally and call their common size $W^{\mathrm{\prime }}$. From step 1.1, ${\gamma }_1,{\gamma }_3<\delta$ and ${\gamma }_2<2\delta$. Hence ${\gamma }_0\le 3\delta -2$ and $W^{\mathrm{\prime }}\ge W{2}^{-9\delta +6}\ge 64ϵn$.

Let $s=\mathrm{\mid }S({\gamma }_3)\mathrm{\mid }$ and $t=\mathrm{\mid }T(\delta ,\beta )\mathrm{\mid }$, so $s,t\le {\delta }^{\eta +1}$, and put $h=k+1-s-t$. The anchor length bound gives $h\ge K-2{\delta }^{\eta +1}({\gamma }_0+1)\ge 2{\delta }^{\eta +1}\ge 2$ because $K\ge 6{\delta }^{\eta +2}$ and ${\gamma }_0+1\le 3\delta -1$. Put $r=\lceil W^{\mathrm{\prime }}-\rho W\rceil$; then $r\ge 63\rho W\ge 63ϵn$. Support-uniformity gives a left-rainbow $S({\gamma }_3)$ on the consecutive blocks $B_h,\dots ,B_{h+s-1}$ and a right-rainbow $T(\delta ,\beta )$ on $B_{h+s},\dots ,B_k$. Greedily pack $r$ pairwise vertex-disjoint copies $E_1,\dots ,E_r$ of the former in the corresponding $C$-blocks, and $r$ pairwise vertex-disjoint copies $F_1,\dots ,F_r$ of the latter. Indeed, if a maximal packing had $r^{\mathrm{\prime }}<r$ members, removing its vertices from each used $C$-block would leave width $W^{\mathrm{\prime }}-r^{\mathrm{\prime }}\ge \rho W$, contradicting $(\rho ,\tau )$-support-invariance of the appropriate sub-blockade of $\mathcal{B}$. The two packings use disjoint intervals of blocks.

For $D\subseteq C_1\cup C_K$, let $a(D)$ count the indices $i\in [r]$ for which $D$ meets $E_i\cup F_i$, and let $b(D)$ count those for which it meets a nonroot vertex. Choose $D$ inclusion-maximal subject to $a(D)\le r\mathrm{/}2$ and $b(D)\ge a(D)\mathrm{/}4$. At least $r\mathrm{/}2\ge ϵn$ roots of the $E_i$ have no neighbor in $D$, so coherence implies $\mathrm{\mid }D\mathrm{\mid }<ϵn$. The untouched roots in $B_h$ and $B_k$ also show that $D$ $\lambda$-misses both blocks. Concavity therefore says that $D$ does not $\lambda$-cover any of $B_{h+1},\dots ,B_{k-1}$. Every internal meeting of an $E_i\cup F_i$ uses a nonroot vertex in those interior blocks, so $b(D)\le \lambda (s+t-2)W$. Since $s+t\le 2{\delta }^{\eta +1}$, $\lambda \le \rho {\delta }^{-\eta -1}$, and $r\ge 63\rho W$, we get $a(D)\le 4b(D)\le 8\rho W\le 8r\mathrm{/}63\le r\mathrm{/}2-ϵn$.

Let $Z\subseteq (C_1\cup C_K)\setminus D$ be the vertices meeting at least one $E_i\cup F_i$, and let $C\subseteq [r]$ be the indices whose $E_i\cup F_i$ is anticomplete to $D$. Since $r\ge ϵn$, coherence bounds the vertices of $C_1\cup C_K$ missing every $E_i\cup F_i$ by $<ϵn$; hence $\mathrm{\mid }Z\mathrm{\mid }>2W^{\mathrm{\prime }}-2ϵn$. Every $v\in Z$ meets at least one pair indexed by $C$: otherwise adjoining it to $D$ leaves $a$ unchanged and cannot decrease $b$, contrary to maximality. If $v\in Z$, the number of $i\in C$ it meets internally is less than one quarter of the number it meets at all. Otherwise $D\cup \{v\}$ would satisfy the two defining inequalities of $D$: its new $a$ is at most $a(D)+ϵn\le r\mathrm{/}2$ (one vertex has fewer than $ϵn$ neighbors among the disjoint rooted trees), and its new $b$ would be at least a quarter of its new $a$. More directly, maximality says $b(D\cup \{v\})<a(D\cup \{v\})\mathrm{/}4$; subtract $b(D)\ge a(D)\mathrm{/}4$.

Order the indices of $C$ uniformly at random. For each $v\in Z$, the first pair it meets among $C$ is met properly (at one or both roots but at no nonroot vertex) with probability $>3\mathrm{/}4$ by step 5.1. On each side $C_1,C_K$, the probability that fewer than half its vertices of $Z$ are proper-first is $<1\mathrm{/}2$: otherwise the expected number of proper-first vertices on that side would be at most three quarters of its size. Thus one order makes both sides at least half proper-first. Relabel all pairs so that the chosen order of $C$ occupies the initial segment $1,\dots ,\mathrm{\mid }C\mathrm{\mid }$, with every pair outside $C$ placed afterward, and call the set of proper-first vertices $X$. Then $\mathrm{\mid }X\cap C_1\mathrm{\mid }\ge \mathrm{\mid }Z\cap C_1\mathrm{\mid }\mathrm{/}2$ and likewise at $C_K$; moreover each side has at least $W^{\mathrm{\prime }}\mathrm{/}2-ϵn$ vertices in $X$. Each $v\in X$ has a first proper meeting index, its happiness, and one of four types $(1,E),(1,F),(K,E),(K,F)$ according to its side and which root it meets.