TheoremStatement: AI-adaptedProof: Literature-sourcedprecheck passaudited 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 without a large pure pair contains a rainbow forest or its complement

Statement

For every forest $F$ there exist integers $r \geq ∣ V (F) ∣$ and a real $σ \in (0, 1)$ such that the following holds. Let $B = (B_{1}, \dots, B_{t})$ be a blockade in a graph $G$ with $t \geq r$ . Then at least one of the following holds:

$B$ has a pure subblockade of length $2$ and width at least $σ width (B)$ ;
$G$ contains a $B^{'}$ -rainbow induced copy of $F$ for some subblockade $B^{'}$ of $B$ of length $∣ V (F) ∣$ ;
$G$ contains a $B^{''}$ -rainbow induced copy of $\overline{F}$ for some subblockade $B^{''}$ of $B$ of length $∣ V (F) ∣$ .

Facts & Assumptions

Given: A forest $F$ , a graph $G$ , and a blockade $B = (B_{1}, \dots, B_{t})$ with $t \geq r$ .

[L1]

A subblockade whose cross-relations match the edge and nonedge pattern of $F$ yields a rainbow induced copy of $F$ (A wide coherent blockade contains a blockade-rainbow copy of a forest).

[L2]

If a graph has sufficiently few induced copies of a fixed graph, then it contains a linearly large induced subgraph whose graph or complement has bounded maximum degree (Few induced copies force a linearly large induced subgraph with bounded maximum degree).

Proof

technique · translate the cited source theorem

1.1

The cited source theorem combines the bounded-degree consequence [L2] with the rainbow-copy criterion [L1] and produces constants $d > 0$ and $K$ such that any blockade of length at least $K$ and width $W$ either contains a pure pair $A, B$ with $∣ A ∣, ∣ B ∣ \geq W / d$ or has a blockade-rainbow copy of one of $F, \overline{F}$ .

L1L2given

2.1

Taking $r : = K$ and $σ : = 1 / d$ , and viewing a pure pair as a pure subblockade of length $2$ and width at least $σ width (B)$ , converts the source conclusion into exactly conclusions 1, 2, and 3 above.

step 1.1

3.1

Therefore the present statement follows.

step 2.1∎

Depends on

Used by

A long blockade yields a wide cograph-pattern subblockade or a rainbow forest Theorem

Dependency tree · two levels

17 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.6 (standard reference, not scraped)