The Erdős–Hajnal Theorems for the E-Graph and Bird — Examples

The identity map on $\{0,1,2,3,4\}$ preserves adjacency and nonadjacency, so it is an induced embedding of $P_5$ in itself by [L3]; hence $P_5$ is not $P_5$-free.

The six-element set $\{p_1,\dots ,p_5,q\}$ has no injection into the five-element set $\{0,1,2,3,4\}$; hence no induced embedding of $E$ in $P_5$ exists, and $P_5$ is $E$-free.

Suppose the finite graph $G$ is not $E$-free. By [L3] there is an induced embedding $\phi$ of $E$ in $G$. Its restriction ${\phi }^{\mathrm{\prime }}$ to $\{p_1,\dots ,p_5\}$ is again an injection preserving adjacency and nonadjacency, and by [L1] the induced subgraph of $E$ on those five vertices has exactly the edges $p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5$, which is a $P_5$ under [L2]. So ${\phi }^{\mathrm{\prime }}$ is an induced embedding of $P_5$ in $G$, and $G$ is not $P_5$-free. Contrapositively, every $P_5$-free graph is $E$-free.

By step 1.3 the class of $P_5$-free graphs is contained in the class of $E$-free graphs, and the containment is strict because the graph $P_5$ itself is $E$-free by step 1.2 yet is not $P_5$-free by step 1.1.

The $E$ theorem [L4] bounds every nonempty graph in the larger $E$-free class, hence in particular every nonempty graph in the $P_5$-free class, whereas the earlier $P_5$ theorem [L5] concerns only that smaller class. Since both theorems merely assert the existence of positive exponents, step 2.1 is a strict inclusion of hypothesis classes and implies no comparison between the two exponents.

The witness $P_5$, the general inclusion of step 1.3 and the strictness of step 2.1 verify all assertions of the example.

The identity map on $\{x_1,x_2,x_3,y,z\}$ preserves adjacency and nonadjacency, so it is an induced embedding of the bull in itself by [L3]; hence the bull is not bull-free.

The six-element set $\{x_1,x_2,x_3,y,z,w\}$ has no injection into the five-element set $\{x_1,x_2,x_3,y,z\}$; hence no induced embedding of Bird in the bull exists, and the bull is Bird-free.

Suppose the finite graph $G$ is not Bird-free. By [L3] there is an induced embedding $\psi$ of Bird in $G$. Its restriction ${\psi }^{\mathrm{\prime }}$ to $\{x_1,x_2,x_3,y,z\}$ is again an injection preserving adjacency and nonadjacency, and by [L1] and [L2] the induced subgraph of Bird on those five vertices is exactly the bull, with the same edge set $x_1{x}_2,x_2{x}_3,x_1{x}_3,x_{1}y,x_{2}z$. So ${\psi }^{\mathrm{\prime }}$ is an induced embedding of the bull in $G$, and $G$ is not bull-free. Contrapositively, every bull-free graph is Bird-free.

By step 1.3 the class of bull-free graphs is contained in the class of Bird-free graphs, and the containment is strict because the bull itself is Bird-free by step 1.2 yet is not bull-free by step 1.1.

The Bird theorem [L4] bounds every nonempty graph in the larger Bird-free class, hence in particular every nonempty graph in the bull-free class, whereas the earlier bull theorem [L5] concerns only that smaller class. Since both theorems merely assert the existence of positive exponents, step 2.1 is a strict inclusion of hypothesis classes and implies no comparison between the two exponents.

The witness bull, the general inclusion of step 1.3 and the strictness of step 2.1 verify all assertions of the example.