LemmaStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Mixed-block reachability is an equivalence relation

Statement

For every blockade, the mixed-block reachability relation $M$ is an equivalence relation on its set of blocks.

Facts & Assumptions

Given: A blockade $L$ with mixed-block reachability relation $M$ .

[L1]

Mixedness of disjoint vertex sets is symmetric (Purity is symmetric; complementation swaps complete and anticomplete pairs and preserves mixed pairs).

[L2]

By definition, $A M B$ means that $A = B$ or that there is a finite chain from $A$ to $B$ through consecutive mixed block pairs (The mixed-block reachability relation on a blockade).

Proof

technique · direct

1.1L2

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

1.2L1L2algebra

If $A 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 M A$ . Thus $M$ is symmetric.

1.3L2algebra

If $A M B$ and $B 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 M C$ . Thus $M$ is transitive.

2.1step 1.1step 1.2step 1.3∎

Therefore $M$ is reflexive, symmetric, and transitive, hence an equivalence relation.

Depends on

Used by

Dependency tree · two levels

5 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Section 6 (standard reference, not scraped)