Small-Graph Erdős-Hajnal Consequences — Examples

Deleting any leaf gives the bull. For instance, after deleting ${\mathrm{\ell }}_1$ the triangle $t_1{t}_2{t}_3$ remains, with leaves ${\mathrm{\ell }}_2$ at $t_2$ and ${\mathrm{\ell }}_3$ at $t_3$; by [L2] this is the bull. The same argument works for deleting ${\mathrm{\ell }}_2$ or ${\mathrm{\ell }}_3$.

To check primeness, let $M$ be a nontrivial module. First, $M$ cannot contain two leaves: if it contains ${\mathrm{\ell }}_i,{\mathrm{\ell }}_j$ and omits one support, that support sees its own leaf but not the other; if it contains both supports as well, then either the remaining triangle vertex or the remaining leaf splits the set. Hence $M$ contains at most one leaf.

Now $M$ cannot contain one leaf together with another vertex. If ${\mathrm{\ell }}_i,t_i\in M$, then another triangle vertex is adjacent to $t_i$ but not to ${\mathrm{\ell }}_i$. If ${\mathrm{\ell }}_i\in M$ and $t_i\mathrm{\notin }M$, then any other vertex of $M$ is either another leaf, excluded by step 1.2, or some $t_j$ with $j\mathrm{\ne }i$, and then ${\mathrm{\ell }}_j$ is outside $M$ and adjacent to $t_j$ but not to ${\mathrm{\ell }}_i$. Therefore a module containing a leaf must be the singleton $\{{\mathrm{\ell }}_i\}$.

Consequently a nontrivial module contains no leaves, so it is a subset of $\{t_1,t_2,t_3\}$ with at least two vertices. But if $t_i,t_j\in M$, then the outside leaf ${\mathrm{\ell }}_i$ is adjacent to $t_i$ and not to $t_j$, so $M$ is not a module. This contradiction shows that no nontrivial module exists. By [L1], the graph is prime.

By [L1], the identity map on the common label set is an isomorphism from the right graph to the complement of the left graph.

Since the left graph is prime by [L2], [L3] says it has no nontrivial module. By [F1], its complement also has no nontrivial module. Therefore the right graph is prime by [L3].

Thus the right six-vertex prime $\mathcal{H}$-graph is the complement of the left one and is prime.

By [L1] and [L2], the vertices $p_1,p_2,p_3,p_4,p_5$ induce a $P_5$, and the extra vertex $q$ is adjacent only to the middle vertex $p_3$. So the labelled graph is exactly the $E$-graph.

Taking the complement toggles each nonedge to an edge and each edge to a nonedge on the same six vertices. By [L1], that complement is co-$E$.

By [L1] and [L2], the vertices $\{x_1,x_2,x_3,y,z\}$ span the bull, and the new vertex $w$ is adjacent only to the horn vertex $y$. Therefore the labelled graph is exactly the Bird graph.

By [L1], co-Bird is obtained by complementing that six-vertex graph on the same label set.

By [L1], the rim vertices $v_1,\dots ,v_5$ induce a $C_5$.

The same fact [L1] says that the remaining vertex $w$ is adjacent to every rim vertex and that no other edges are present. This is exactly the five-wheel.

By [L1], $H_1$ keeps all edges of $H_0$ and adds exactly one new edge $v_1{v}_1^{\mathrm{\prime }}$. So $H_1$ is precisely the five-wheel with one pendant leaf at $v_1$.

Repeating the same operation for $i=2,3,4,5$ adds the leaves $v_2^{\mathrm{\prime }},v_3^{\mathrm{\prime }},v_4^{\mathrm{\prime }},v_5^{\mathrm{\prime }}$ one at a time and changes no earlier adjacencies. Hence $H_5$ is the graph obtained from $H_0$ by attaching one leaf to each rim vertex $v_i$.