External purity survives every E overlap quotient

Complete nonedge pairs force purity on induced E graphs supplies the following statement: Let $G$ be a finite simple co-Bird-free graph. Let $x,y,u$ be distinct vertices outside the indicated induced subgraph, with $xy\mathrm{\notin }E(G)$, $ux\in E(G)$ and $uy\mathrm{\notin }E(G)$, and with $x,y$ complete to that subgraph. Let $S=\{p_1,p_2,p_3,p_4,p_5,q\}$ induce $E$, with edges exactly $p_1{p}_2,p_2{p}_3,p_3{p}_4,p_4{p}_5,p_{3}q$. Then $u$ is pure to $S$. In particular, in an $(\mathrm{\ell },w)$-comb with an outside vertex $v$ complete to all blocks and anticomplete to all teeth, each $u\in B_k$, $k\mathrm{\ne }i$, is pure to every induced $E$ in $B_i$.

Purity propagates through E overlap chains supplies the following statement: Fix a comb block $B_i$ and an $E$ overlap class $A$. If $u\mathrm{\notin }A$ is pure to every induced $E$ contained in $A$, then $u$ is pure to $A$. In particular, any $u\mathrm{\notin }{B}_i$ pure to every induced $E$ in $B_i$ is pure to every overlap class.

The E overlap blockade and mixed quotient sequence supplies the following definition: Fix a comb block $B_i$ with nonempty $E$ overlap support $X_i$. By lem-e-overlap-classes-form-an-anticonnected-partition, its overlap classes are nonempty anticonnected sets partitioning $X_i$. Fix an enumeration of the finite set $B_i$, and order the classes by their least enumerated vertex to obtain ${\mathcal{L}}^1$. Define recursively ${\mathcal{L}}^{s+1}={\mathcal{L}}^s\mathrm{/}\mathcal{M}$ for $s\ge 1$, using def-quotient-blockade-by-mixed-block-reachability and its least-member ordering. Thus one replaces each mixed-reachability class of blocks by its union. This construction is used only when $X_i\mathrm{\ne }\mathrm{\varnothing }$.

E overlap quotients terminate at a pure blockade supplies the following statement: For nonempty overlap support, put $n=\mathrm{\mid }{\mathcal{L}}^1\mathrm{\mid }$. Every stage ${\mathcal{L}}^s$ partitions the same support into nonempty anticonnected blocks and coarsens ${\mathcal{L}}^1$. There is a least $q\ge 1$ for which ${\mathcal{L}}^q$ is pure, with $q\le n$. At most $n-1$ strict transitions occur, and all stages from $q$ onward are identical.

A separated anticonnected block pair forbids mixing in one direction supplies the following statement: Let $G$ be finite simple and co-Bird-free. Let $D_1,D_2$ be disjoint nonempty vertex sets, with $D_2$ anticonnected. Suppose distinct $x,y,z\mathrm{\notin }{D}_1\cup D_2$ satisfy $xy\mathrm{\notin }E(G)$, both $x,y$ are complete to $D_1\cup D_2$, $zx\in E(G)$, $zy\mathrm{\notin }E(G)$, and $z$ is complete to $D_1$ and anticomplete to $D_2$. Then no vertex of $D_1$ is mixed on $D_2$.

A vertex mixed on a quotient block but pure on each member block yields two mixed member blocks with opposite adjacency supplies the following statement: Let $D$ be a block of the quotient blockade $\mathcal{L}\mathrm{/}\mathcal{M}$, and let $u\mathrm{\notin }D$ be a vertex. Suppose that $u$ is mixed on $D$ but is pure to every original block of $\mathcal{L}$ contained in $D$. Then there are two original blocks $A_1,A_2$ of $\mathcal{L}$, both contained in $D$, such that 1. $A_1$ and $A_2$ are mixed; and 2. $u$ is complete to $A_1$ and anticomplete to $A_2$.

A quotient-level mixed-block witness descends to two mixed member blocks supplies the following statement: Let $\mathcal{L}$ be a blockade in a graph $G$, and suppose that every block of $\mathcal{L}$ is connected or every block is anticonnected. Let $D_1,D_2$ be distinct mixed blocks of the quotient blockade $\mathcal{L}\mathrm{/}\mathcal{M}$. Assume there are vertices $x,y,u\mathrm{\notin }{D}_1\cup D_2$ such that: 1. $x$ and $y$ are nonadjacent and both are complete to $D_1\cup D_2$; 2. $u\in N(x)\setminus N(y)$, with $u$ complete to $D_1$ and anticomplete to $D_2$; and 3. no vertex of $D_1$ is mixed on $D_2$. Then there are mixed original blocks $A_1,A_2$ of $\mathcal{L}$, both contained in $D_1$, and vertices $x^{\mathrm{\prime }},y^{\mathrm{\prime }},u^{\mathrm{\prime }}\mathrm{\notin }{A}_1\cup A_2$ such that: 1. $x^{\mathrm{\prime }}$ and $y^{\mathrm{\prime }}$ are nonadjacent and both are complete to $A_1\cup A_2$; and 2. $u^{\mathrm{\prime }}\in N(x^{\mathrm{\prime }})\setminus N(y^{\mathrm{\prime }})$, with $u^{\mathrm{\prime }}$ complete to $A_1$ and anticomplete to $A_2$.

Combs in a graph supplies the following definition: Let $\mathrm{\ell }\in \mathbb{N}$ with $\mathrm{\ell }\ge 1$, and let $w>0$. An $(\mathrm{\ell },w)$-comb in a graph $G$ is a sequence of pairs $((a_i,B_i):i\in [\mathrm{\ell }])$ satisfying the conditions below. Here a vertex $a$ is complete to (respectively, anticomplete to) a set $B$ when the pair $(\{a\},B)$ is complete (respectively, anticomplete) in the sense of def-edges-between-sets-and-pure-mixed-pairs. 1. $(B_1,\dots ,B_{\mathrm{\ell }})$ is an $(\mathrm{\ell },w)$-blockade; 2. the vertices $a_1,\dots ,a_{\mathrm{\ell }}$ are distinct; 3. the set $\{a_1,\dots ,a_{\mathrm{\ell }}\}$ is disjoint from every block $B_i$; and 4. for every $i\in [\mathrm{\ell }]$, the vertex $a_i$ is complete to $B_i$; and 5. for all distinct $i,j\in [\mathrm{\ell }]$, the vertex $a_i$ is anticomplete to $B_j$. The vertices $a_i$ are the teeth of the comb.