Leaf Reducibility and Wonderful Families

By [L2], choose $p,q\in A$ with $vp\in E(G)$ and $vq\mathrm{\notin }E(G)$. Since $A$ is anticonnected, [L1] gives a path $p=x_0,x_1,\dots ,x_m=q$ in the complement graph $\bar{G}[A]$.

Along that path, the truth value of "$v{x}_i\in E(G)$" changes from true at $i=0$ to false at $i=m$. Hence there exists $k<m$ such that $v{x}_k\in E(G)$ and $v{x}_{k+1}\mathrm{\notin }E(G)$.

Because $x_k{x}_{k+1}$ is an edge of $\bar{G}[A]$, it is a nonedge of $G$. Therefore $b:=x_k$ and $b^{\mathrm{\prime }}:=x_{k+1}$ satisfy $b{b}^{\mathrm{\prime }}\mathrm{\notin }E(G)$, $vb\in E(G)$, and $v{b}^{\mathrm{\prime }}\mathrm{\notin }E(G)$, which is the conclusion.

For each $i\in [s]$, apply [L1] to choose nonadjacent vertices $b_i,b_i^{\mathrm{\prime }}\in B_i$ with $v{b}_i\in E(G)$ and $v{b}_i^{\mathrm{\prime }}\mathrm{\notin }E(G)$.

Now assume $J[\{1,\dots ,q\}]=F$ and $(q-1)\eta <1$. Choose $x_1\in B_1$ arbitrarily. Suppose $x_1,\dots ,x_{j-1}$ have been chosen with $2\le j\le q$, so that for all $1\le i<k<j$ one has $x_i{x}_k\in E(G)$ if and only if $ik\in E(F)$.

Assume instead that $J[\{1,\dots ,q\}]=H$, that $12\in E(H)$, and that $(q-1)\eta <\frac{1}{2}$. Because $0<\mathrm{\mid }{N}_G(v)\cap B_i\mathrm{\mid }$ for $i=1,2$, choose $x_1\in B_1$ and $x_2\in B_2$ adjacent to $v$. Since $12\in E(H)=E(J[\{1,\dots ,q\}])$, the pair $(B_1,B_2)$ is complete, so $x_1{x}_2\in E(G)$. Suppose now that $x_1,\dots ,x_{j-1}$ have been chosen with $3\le j\le q$ so that $v{x}_1,v{x}_2\in E(G)$, $v{x}_i\mathrm{\notin }E(G)$ for $3\le i<j$, and $x_i{x}_k\in E(G)$ if and only if $ik\in E(H)$ for all $1\le i<k<j$.

Let $X=\{i_1,\dots ,i_t\}$ be a clique in $J$. By definition of $J$, the pairs $(B_{i_r},B_{i_u})$ are complete for all $r\mathrm{\ne }u$, so every vertex chosen from one selected block is adjacent to every vertex chosen from another selected block. Together with step 1.1, this shows that on the vertex set $\{v,b_{i_1},b_{i_1}^{\mathrm{\prime }},\dots ,b_{i_t},b_{i_t}^{\mathrm{\prime }}\}$ the only nonedges are $v{b}_{i_r}^{\mathrm{\prime }}$ and $b_{i_r}{b}_{i_r}^{\mathrm{\prime }}$ for $r\in [t]$. That is exactly the nonedge pattern of the complement of the $1$-subdivision of $K_{1,t}$, with $v$ as the complemented center, $b_{i_r}^{\mathrm{\prime }}$ as the subdivision vertex, and $b_{i_r}$ as the corresponding leaf.

For each $i<j$ with $ij\mathrm{\notin }E(F)=E(J[\{1,\dots ,q\}])$, the pair $(B_i,B_j)$ is not complete, so hypothesis 3 and [L3] imply that $x_i$ has at most $\eta \mathrm{\mid }{B}_j\mathrm{\mid }$ neighbours in $B_j$. Therefore at most $(j-1)\eta \mathrm{\mid }{B}_j\mathrm{\mid }$ vertices of $B_j$ violate one of the required nonadjacency conditions to the previously chosen vertices. Since $(q-1)\eta <1$ and $j-1\le q-1$, some vertex $x_j\in B_j$ avoids all those forbidden sets. For such a choice, every required edge holds automatically because whenever $ij\in E(F)=E(J)$ the pair $(B_i,B_j)$ is complete.

By induction on $j$, steps 1.2 and 2.2 produce vertices $x_1,\dots ,x_q$ with $x_i{x}_j\in E(G)$ if and only if $ij\in E(F)$ for all distinct $i,j\in [q]$. Hence $G[\{x_1,\dots ,x_q\}]$ is an induced copy of $F$. This proves assertion 2.

For $j\ge 3$, hypothesis 2 gives fewer than $\frac{1}{2}\mathrm{\mid }{B}_j\mathrm{\mid }$ neighbours of $v$ in $B_j$, so more than $\frac{1}{2}\mathrm{\mid }{B}_j\mathrm{\mid }$ vertices of $B_j$ are nonadjacent to $v$. As in step 2.2, the nonedge requirements to the previously chosen $x_i$ exclude at most $(j-1)\eta \mathrm{\mid }{B}_j\mathrm{\mid }<(q-1)\eta \mathrm{\mid }{B}_j\mathrm{\mid }<\frac{1}{2}\mathrm{\mid }{B}_j\mathrm{\mid }$ further vertices. Hence some $x_j\in B_j$ is simultaneously nonadjacent to $v$ and satisfies $x_i{x}_j\in E(G)$ if and only if $ij\in E(H)$ for every $i<j$. Inducting on $j$ produces vertices $x_1,\dots ,x_q$ such that the old vertices induce $H$, the new vertex $v$ is adjacent exactly to $x_1$ and $x_2$, and therefore $G[\{v,x_1,\dots ,x_q\}]$ is an induced copy of $H^{+}$ by [L4]. This proves assertion 3.

[assume-case star] Assume condition 1, with $F_{\star }$ an induced subgraph of the $1$-subdivision of $K_{1,t}$. If $J$ had a clique of size $t$, then [L1] would give an induced copy of the complement of that $1$-subdivision in $G$. Because complementation preserves induced-subgraph containment, $\overline{F_{\star }}$ would then occur as an induced subgraph of $G$. But $\overline{F_{\star }}\in \bar{\mathcal{F}}$, contradicting that $G$ is $\bar{\mathcal{F}}$-free. So $J$ is $K_t$-free.

[assume-case special] Assume condition 2, and write $\mathcal{G}:=\{H\}\cup \bar{\mathcal{F}}$. By the Erdős-Hajnal property of $\mathcal{G}$, [L3] gives an Erdős-Hajnal constant $ϵ>0$ for $\mathcal{G}$. Put $c:=\min \{ϵ,\frac{1}{2}\}\in (0,1)$. Then every nonempty $\mathcal{G}$-free graph $X$ satisfies $\mathrm{hom}(X)\ge \mathrm{\mid }V(X){\mathrm{\mid }}^c$.

[assume-case star] By [L2] and [L3], the class of $K_t$-free graphs has an Erdős-Hajnal constant $ϵ>0$. Put $c:=\min \{ϵ,\frac{1}{2}\}\in (0,1)$. Since $s\ge 1$, the graph $J$ is nonempty, so applying the bound to the $K_t$-free graph $J$ from step 1.1 and then using [L4], $J$ has a clique or a stable set of size at least $\mathrm{\mid }J{\mathrm{\mid }}^c$.

[assume-case special] We claim that $J$ is $\mathcal{G}$-free. If $J$ contained an induced copy of some $F\in \bar{\mathcal{F}}$ with $r:=\mathrm{\mid }V(F)\mathrm{\mid }$, then $r\le m\le a$, so $(r-1)y^a\le (r-1)2^{-a}\le (r-1)2^{-r}<1$. Relabel the indices of that copy as $[r]$; [L1] then lifts it to an induced copy of $F$ in $G$, contradicting that $G$ is $\bar{\mathcal{F}}$-free. If $J$ contained an induced copy of $H$, relabel its indices as $[q]$. Since $q\le m\le a$ gives $(q-1)y^a<(q-1)2^{-a}\le (q-1)2^{-q}<\frac{1}{2}$, [L1] lifts it to an induced copy of $H^{+}$ in $G$. Since $H^{+}$ is not $\bar{\mathcal{F}}$-free by hypothesis, that would again contradict the $\bar{\mathcal{F}}$-freeness of $G$. Hence $J$ is $\mathcal{G}$-free.

[assume-case special] Since $s\ge 1$, applying step 1.2 to the nonempty $\mathcal{G}$-free graph $J$ and then using [L4], we obtain a clique or a stable set in $J$ of size at least $\mathrm{\mid }J{\mathrm{\mid }}^c$.

Steps 2.1 and 3.1 cover the two hypotheses in the Statement. In the star case, $c$ depends only on $t$; in the special case, it depends only on $\mathcal{G}=\{H\}\cup \bar{\mathcal{F}}$. Thus the chosen $c$ is independent of $a,y,G,v$, and the blocks, and $J$ has a clique or a stable set of size at least $\mathrm{\mid }J{\mathrm{\mid }}^c$.

Let $m$ be the common block size. Since $\mathrm{\mid }I\mathrm{\mid }\ge y\mathrm{\ell }$, $\mathrm{\ell }\ge y^{-a}$, and $r\ge \mathrm{\mid }I{\mathrm{\mid }}^c$, we have $r^{-1}\le \mathrm{\mid }I{\mathrm{\mid }}^{-c}\le (y\mathrm{\ell }{)}^{-c}\le y^{c(a-1)}\le y^5$.

Now suppose that $R$ is a stable set in $J$. For any $x\in B_i\subseteq S$, the neighbours of $x$ inside its own block contribute fewer than $m=r^{-1}\mathrm{\mid }S\mathrm{\mid }$ vertices. If $j\in R\setminus \{i\}$, then $ij\mathrm{\notin }E(J)$, so the pairs $(B_i,B_j)$ are mutually $y^a$-sparse and [L2] gives at most $y^a\mathrm{\mid }{B}_j\mathrm{\mid }$ neighbours of $x$ in $B_j$. Summing over all other selected blocks, $x$ has at most $r^{-1}\mathrm{\mid }S\mathrm{\mid }+y^a{\sum }_{j\in R\setminus \{i\}}\mathrm{\mid }{B}_j\mathrm{\mid }\le (r^{-1}+y^a)\mathrm{\mid }S\mathrm{\mid }$ neighbours in $S$.

First suppose that $R$ is a clique in $J$. Then [L3] makes every two distinct selected blocks complete. For any $x\in B_i\subseteq S$, the only possible nonneighbours of $x$ inside $S$ lie in $B_i$, so $x$ has fewer than $m=r^{-1}\mathrm{\mid }S\mathrm{\mid }$ nonneighbours in $S$. Step 1.1 gives $r^{-1}\mathrm{\mid }S\mathrm{\mid }\le y^5\mathrm{\mid }S\mathrm{\mid }\le y^4\mathrm{\mid }S\mathrm{\mid }$, so $S$ is $y^4$-dense and hence $y^4$-restricted by [L1].

Since $a\ge 5\mathrm{/}c+1$ and $y<\frac{1}{2}$, step 1.1 yields $r^{-1}+y^a\le y^5+y^a\le y^5+y^5\le y^4$. Hence every vertex of $S$ has at most $y^4\mathrm{\mid }S\mathrm{\mid }$ neighbours inside $S$, so $S$ is $y^4$-sparse and therefore $y^4$-restricted by [L1].

Steps 2.1 and 2.2 show that whether $R$ is a clique or a stable set, the union $S$ is $y^4$-restricted. Also $\mathrm{\mid }S\mathrm{\mid }=rm\ge m$, so $S$ has at least the common block size.

Choose $a_0:=1$ in case 1. In case 2, let $a_0$ be the maximum order of a graph in $\{H\}\cup \bar{\mathcal{F}}$. By [L2], fix a constant $c\in (0,1)$ suitable for the corresponding obstruction hypothesis, and then choose $a\ge \max \{6,a_0,5\mathrm{/}c+1\}$.

Let $y\in (0,\frac{1}{2})$, let $G$ be a $\bar{\mathcal{F}}$-free graph, and let $\mathcal{B}=(B_1,\dots ,B_{\mathrm{\ell }})$ be an $(\mathrm{\ell },w)$-blockade satisfying the hypotheses from [L1] for the constant $a$. For each outside vertex $x\in V(G)\setminus V(\mathcal{B})$, define $I(x):=\{i\in [\mathrm{\ell }]:0<\mathrm{\mid }{N}_G(x)\cap B_i\mathrm{\mid }<\frac{1}{2}\mathrm{\mid }{B}_i\mathrm{\mid }\}$. Suppose first that $\mathrm{\mid }I(x)\mathrm{\mid }\le y\mathrm{\ell }$ for every such $x$. Then the number of pairs $(x,i)$ with $x\in V(G)\setminus V(\mathcal{B})$ and $i\in I(x)$ is at most $y\mathrm{\ell }\mathrm{\mid }V(G)\setminus V(\mathcal{B})\mathrm{\mid }\le y\mathrm{\ell }\mathrm{\mid }V(G)\mathrm{\mid }$. Averaging over the $\mathrm{\ell }$ indices, some $i\in [\mathrm{\ell }]$ is contained in at most $y\mathrm{\mid }V(G)\mathrm{\mid }$ of the sets $I(x)$. That is exactly the second conclusion from [L1].

It remains to consider the opposite case. Choose $v\in V(G)\setminus V(\mathcal{B})$ with $\mathrm{\mid }I(v)\mathrm{\mid }\ge y\mathrm{\ell }$. Let $\rho :[s]\to I(v)$ be the increasing bijection, where $s=\mathrm{\mid }I(v)\mathrm{\mid }$, put $C_j:=B_{\rho (j)}$, and form the auxiliary graph $J$ on $[s]$ by $ij\in E(J)$ if and only if $C_i$ is complete to $C_j$. The reordered family of blocks still has equal size, still satisfies $s\ge y\mathrm{\ell }$, and still satisfies the pairwise complete-or-mutually-$y^a$-sparse hypothesis. Therefore [L2] applies and gives a clique or stable set $R\subseteq [s]$ with $\mathrm{\mid }R\mathrm{\mid }\ge s^c$.

Put $R^{\mathrm{\prime }}:=\rho (R)\subseteq I(v)$. In the auxiliary graph on the original index set $I(v)$, the set $R^{\mathrm{\prime }}$ is a clique or stable set with $\mathrm{\mid }{R}^{\mathrm{\prime }}\mathrm{\mid }=\mathrm{\mid }R\mathrm{\mid }\ge \mathrm{\mid }I(v){\mathrm{\mid }}^c$. The original blockade $\mathcal{B}$ has length $\mathrm{\ell }\ge y^{-a}$, the subset $I(v)$ has size at least $y\mathrm{\ell }$, and $a\ge 5\mathrm{/}c+1$. Thus [L3] applies to $\mathcal{B}$, $I(v)$, and $R^{\mathrm{\prime }}$. It follows that ${\bigcup }_{i\in R^{\mathrm{\prime }}}{B}_i$ induces a $y^4$-restricted subgraph of $G$ whose size is at least the common block size, and therefore at least the width $w$ of $\mathcal{B}$. This is the first conclusion from [L1].

Step 1.2 gives the second wonderfulness outcome when no outside vertex belongs to many index sets $I(x)$, and step 3.1 gives the first outcome otherwise. Thus the constant $a$ from step 1.1 satisfies [L1], so $\mathcal{F}$ is wonderful.

For the $E$-graph, take the $1$-subdivision of $K_{1,3}$ with center $c$, subdivision vertices $s_1,s_2,s_3$, and leaves $t_1,t_2,t_3$. On the six-vertex subset $\{t_1,s_1,c,s_2,t_2,s_3\}$, the induced edges are $t_1{s}_1$, $s_{1}c$, $c{s}_2$, $s_2{t}_2$, and $c{s}_3$, which is exactly the edge set of the $E$-graph from The $E$-graph and co-$E$. Thus $E$ is an induced subgraph of the $1$-subdivision of $K_{1,3}$, so [L1] makes $\{E\}$ wonderful.

In the graph $H$ from [A1], the vertices $v_2$ and $v_5$ are adjacent to each other and both have the same neighbourhood outside $\{v_2,v_5\}$, namely $\{v_1,v_3,v_4\}$. Hence $\{v_2,v_5\}$ is a homogeneous clique. Let $Q$ be the five-vertex graph on $\{x,v_1,v_3,v_4,v_6\}$ with edge set $\{x{v}_1,x{v}_3,x{v}_4,v_1{v}_3,v_1{v}_6,v_4{v}_6\}$. Then $H$ is obtained from $Q$ by substituting $K_2$ for the vertex $x$. By [L2], both $Q$ and $K_2$ have the Erdős-Hajnal property, so [L3] gives the Erdős-Hajnal property for $H$.

Form $H^{+}$ from [A1] by adjoining a new vertex $v$ adjacent to $v_1$ and $v_2$, and delete $v_3$. On the remaining six vertices $\{v,v_1,v_2,v_4,v_5,v_6\}$ the edge set is $\{v{v}_1,v{v}_2,v_1{v}_2,v_1{v}_5,v_1{v}_6,v_2{v}_4,v_2{v}_5,v_4{v}_5,v_4{v}_6\}$. Under the relabelling $x_1=v$, $x_2=v_6$, $x_3=v_5$, $y=v_4$, $z=v_2$, and $w=v_1$, the six missing edges are exactly $x_1{x}_2$, $x_1{x}_3$, $x_2{x}_3$, $x_{1}y$, $x_{2}z$, and $yw$, which are precisely the Bird edges. Therefore $H^{+}-v_3$ is co-Bird, so $H^{+}$ is not co-Bird-free.

Step 1.2 shows that $\{H\}\cup \{\mathrm{c}\mathrm{o}\text{-}\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ has the Erdős-Hajnal property, and step 1.3 shows that $H^{+}$ is not co-Bird-free. Therefore [L1] applies to the singleton family $\{\mathrm{B}\mathrm{i}\mathrm{r}\mathrm{d}\}$ and proves that Bird is wonderful. Together with step 1.1, this proves the statement.