TheoremStatement: AI-adaptedProof: Literature-sourcedprecheck passjudge pass (gpt-5.6-terra)audited 2026-08-31

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 long blockade yields a wide cograph-pattern subblockade or a rainbow forest

Statement

Let $F$ be a forest. Then there exists an integer $d \geq 1$ such that for every integer $s \geq 1$ and every graph $G$ with a blockade $B$ of length

$D : = 2^{s - 1} d^{2 s - 1}$

and width $W$ , at least one of the following holds:

$G$ has a pure blockade $A$ of length $2^{s}$ and width at least $W / D$ whose pattern graph is a cograph;
$G$ contains a $B$ -rainbow induced copy of one of $F, \overline{F}$ .

Facts & Assumptions

Given: A forest $F$ , an integer $s \geq 1$ , a graph $G$ , and a blockade $B$ in $G$ of length $D : = 2^{s - 1} d^{2 s - 1}$ and width $W$ .

[L1]

Theorem 6.7 of the cited source proves exactly the displayed alternative after translating its pattern language into the library's blockade notation.

Proof

technique · translate the cited source theorem

1.1

The cited source theorem proves exactly this cograph-pattern or rainbow-copy alternative after translating its pattern language into the library's blockade notation.

L1given

2.1

Therefore the present statement follows.

step 1.1∎

Depends on

Used by

The star-expansion four-family of a forest has the Erdős-Hajnal property Theorem

Dependency tree · two levels

15 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

Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl, Erdős-Hajnal for graphs with no 5-hole, Theorem 6.7 (standard reference, not scraped)