Quotient Blockades and Mixing Relations

Reflexivity is immediate from [L2], because every block is related to itself.

If $A\mathcal{M}B$ by a mixed chain $A=A_1,A_2,\dots ,A_m=B,$ then [L1] makes the reversed chain $B=A_m,A_{m-1},\dots ,A_1=A$ again a mixed chain, so $B\mathcal{M}A$. Thus $\mathcal{M}$ is symmetric.

If $A\mathcal{M}B$ and $B\mathcal{M}C$, then [L2] gives a mixed chain from $A$ to $B$ and another from $B$ to $C$. Concatenating them at $B$ yields a mixed chain from $A$ to $C$, so $A\mathcal{M}C$. Thus $\mathcal{M}$ is transitive.

Therefore $\mathcal{M}$ is reflexive, symmetric, and transitive, hence an equivalence relation.

Assume first that every original block contained in $D$ is connected. Fix one such block $A_0\subseteq D$. Let $B\subseteq D$ be any other member block. By [L1], choose a mixed chain $A_0=B_0,B_1,\dots ,B_m=B$ inside $D$. We prove by induction on $m$ that $G[B_0\cup \cdots \cup B_m]$ is connected. The case $m=0$ is immediate because $B_0=A_0$ is connected. If $m>0$, then the induction hypothesis gives connectedness of $G[B_0\cup \cdots \cup B_{m-1}]$, the block $B_m$ is connected by assumption, and [L2] gives a cross-edge between $B_{m-1}$ and $B_m$ because that pair is mixed. Hence the union up to $B_m$ is connected. Since $B$ was arbitrary, every member block of $D$ lies in the same connected component of $G[D]$, and therefore $G[D]$ is connected.

Now assume every original block contained in $D$ is anticonnected. By [L3] and [L4], each member block induces a connected subgraph of $\bar{G}$. If two member blocks are consecutive on a mixed chain in $D$, then [L2] gives a cross-nonedge between them in $G$, hence a cross-edge in $\bar{G}$. Repeating the argument of step 1.1 inside $\bar{G}$ shows that $\bar{G}[D]$ is connected. By [L3], this means that $G[D]$ is anticonnected.

Steps 1.1 and 2.1 prove the connected and anticonnected conclusions.

Suppose for contradiction that $(A,B)$ is mixed. Then [L2] gives a mixed chain of length one from $A$ to $B$, so $A\mathcal{M}B$.

By [L1], $\mathcal{M}$-related blocks lie in the same quotient block of $\mathcal{L}\mathrm{/}\mathcal{M}$. This contradicts the hypothesis that $A$ and $B$ lie in different quotient blocks.

Therefore $(A,B)$ is not mixed, hence it is pure.

By [L1], choose original blocks $B_1,B_2\subseteq D$ such that $u$ is complete to $B_1$ and anticomplete to $B_2$.

By [L2], choose a mixed block chain $B_1=A_{r_1},A_{r_2},\dots ,A_{r_m}=B_2$ inside $D$. Since $u$ is complete to the first block and anticomplete to the last, there is a first index $j<m$ at which the relation changes. Then $u$ is complete to $A_{r_j}$ and anticomplete to $A_{r_{j+1}}$, and the two blocks are mixed because they are consecutive on the chain.

Taking $A_1:=A_{r_j}$ and $A_2:=A_{r_{j+1}}$ gives the required pair of mixed original blocks in $D$.

Since $D_1$ and $D_2$ are mixed as quotient blocks, there is a vertex in one of them that is mixed on the other. Hypothesis 3 excludes the possibility that a vertex of $D_1$ is mixed on $D_2$, so choose a vertex $b_2\in D_2$ that is mixed on $D_1$.

The quotient blocks $D_1$ and $D_2$ are distinct. Therefore [L1] implies that every original block of $\mathcal{L}$ contained in $D_2$ is pure to every original block of $\mathcal{L}$ contained in $D_1$. In particular, if $B$ is the original block of $\mathcal{L}$ containing $b_2$, then $b_2$ is pure to every original block contained in $D_1$.

Now $b_2$ is outside $D_1$, is mixed on $D_1$ by step 1.1, and is pure to every original block inside $D_1$ by step 2.1. Applying [L2], choose mixed original blocks $A_1,A_2\subseteq D_1$ such that $b_2$ is complete to $A_1$ and anticomplete to $A_2$.

Set $x^{\mathrm{\prime }}:=y$, $y^{\mathrm{\prime }}:=u$, and $u^{\mathrm{\prime }}:=b_2$. Because $y$ is complete to $D_1\cup D_2$, it is complete to $A_1\cup A_2$ and adjacent to $b_2$. Because $u$ is complete to $D_1$ and anticomplete to $D_2$, it is complete to $A_1\cup A_2$ and nonadjacent to $b_2$. Hypothesis 2 gives $u\in N(x)\setminus N(y)$, so $y$ and $u$ are nonadjacent. Therefore $u^{\mathrm{\prime }}=b_2\in N(x^{\mathrm{\prime }})\setminus N(y^{\mathrm{\prime }})$, while $u^{\mathrm{\prime }}$ is complete to $A_1$ and anticomplete to $A_2$ by step 3.1. This is exactly the required witness.