ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-04

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.

A large almost-pure pair extends an anticomplete blockade

Example

Let

$B_{0} = {u_{1}, u_{2}}, B_{1} = {v_{1}, v_{2}}, B_{2} = {w_{1}, w_{2}, w_{3}, w_{4}, w_{5}, w_{6}},$

and assume:

$B_{0}$ is anticomplete to $B_{1}$ ;
$B_{0} \cup B_{1}$ is anticomplete to $B_{2}$ ;
inside $B_{2}$ there are disjoint subsets $X = {w_{1}, w_{2}}, Y = {w_{3}, w_{4}, w_{5}, w_{6}},$ with $Y$ anticomplete to $X$ .

Then $(B_{0}, B_{1}, B_{2})$ is an anticomplete blockade, and replacing the last block $B_{2}$ by the pair $(X, Y)$ produces the longer anticomplete blockade $(B_{0}, B_{1}, X, Y)$ .

Facts & Assumptions

Given: The blocks $B_{0}, B_{1}, B_{2}$ and the subsets $X, Y \subseteq B_{2}$ with the adjacency relations stated in the example.

[L1]

A blockade is an ordered sequence of pairwise disjoint nonempty vertex sets (Blockades, their length, their width, and their support).

[L2]

A pair of disjoint vertex sets is anticomplete exactly when there are no edges between them (Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs).

Verification

technique · direct

1.1

The sets $B_{0}, B_{1}, B_{2}$ are pairwise disjoint and nonempty, so $(B_{0}, B_{1}, B_{2})$ is a blockade by [L1]. Hypotheses 1 and 2 say that each earlier block is anticomplete to every later block, so [L2] makes it an anticomplete blockade.

L1L2given

1.2

The sets $X$ and $Y$ are disjoint nonempty subsets of $B_{2}$ , and hypothesis 3 says that $Y$ is anticomplete to $X$ . Hypothesis 2 also implies that both $X$ and $Y$ are anticomplete to $B_{0} \cup B_{1}$ . Therefore every earlier block in $(B_{0}, B_{1}, X, Y)$ is anticomplete to every later block.

givenL2

2.1

By steps 1.1 and 1.2, replacing the last block $B_{2}$ by the anticomplete pair $(X, Y)$ extends the original anticomplete blockade by one step.

step 1.1step 1.2∎

Depends on

Used by

Nothing in the library uses this result yet.

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, Erdos-Hajnal beyond the five-vertex path, proof of Lemma 2.8 (standard reference, not scraped)