The Five-Cycle and the Erdős-Hajnal Property — Examples

The two teeth $a_1,a_2$ are distinct, the blocks $\{b_1\}$ and $\{b_2\}$ are disjoint, each tooth is adjacent to its own block vertex, and neither tooth is adjacent to the other block. Thus $((a_1,\{b_1\}),(a_2,\{b_2\}))$ is a comb in $G$.

The set $\{a_1,a_2\}$ is stable, the root $v$ is adjacent to both teeth, and $v$ is anticomplete to both blocks. Therefore [L1] identifies the displayed data as a rooted stable-tooth comb.

The underlying five-vertex configuration is still a rooted stable-tooth comb with teeth $a_1,a_2$, blocks $\{b_1\},\{b_2\}$, and root $v$; the new feature is exactly the cross-edge $b_1{b}_2$ between the two blocks.

Applying [L1] with $i=1$ and $j=2$ shows that the induced subgraph on $\{v,a_1,b_1,b_2,a_2\}$ is a copy of $C_5$.

In the given graph, $a_1$ is adjacent to $b_1$ and not to $b_2$, while $a_2$ is adjacent to $b_2$ and not to $b_1$. The teeth are distinct and the singleton blocks are disjoint. Therefore [L1] shows that $((a_1,\{b_1\}),(a_2,\{b_2\}))$ is a comb.

The two blocks are not anticomplete, because the graph was built with the edge $b_1{b}_2$. So this comb refutes the statement that every comb has pairwise anticomplete blocks.

By [L1], there exists a specific comb with two blocks that are not anticomplete.

Therefore the universal statement is false. The anticomplete-block conclusion on the A page needs the extra rooted stable-tooth structure together with $C_5$-freeness, not merely the definition of a comb.