The strong Erdős–Hajnal property implies the Erdős–Hajnal property

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