Small-Graph Erdős-Hajnal Consequences — Examples

By [F1], exactly $c,f$ have degree one and exactly $b$ has degree four. Deleting $f$ leaves edges $ab,bc,ad,bd,be,de$: on $a,b,d,e$ these form a complete graph minus $ae$, with $c$ attached only to $b$. Deleting $b$ leaves exactly $ad,de,ef$ and isolated $c$. Deleting either leaf removes one of the seven edges, leaving six, so neither resulting graph is the five-edge bull.

If a module $M$ contains a set $S$ and a vertex outside $S$ has both a neighbour and a nonneighbour in $S$, that vertex must also belong to $M$. Otherwise it would violate the defining uniform outside adjacency of a module. Thus such vertices can be forced into $M$ successively.

The following table covers every unordered pair of vertices. Starting from the pair in the first column, append the vertices in the second column from left to right. At each append, [F1] shows that the new vertex has a neighbour and a nonneighbour in the set already obtained. Consequently step 1.2 forces all six vertices into every module containing the initial pair.

Every set with at least two vertices contains one of those pairs, so step 2.1 excludes every proper module of size at least two. By [L1], $L$ is prime. Together with step 1.1 this proves all the stated claims.

The left graph has edges $ab,bc,ad,bd,be,de,ef$. The remaining eight of the fifteen unordered vertex pairs are exactly $ac,ae,af,bf,cd,ce,cf,df$, the right graph's edges. Thus the identity 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$.