CorollaryStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)audited 2026-08-26

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.

Rödl's theorem for a nonempty family of forbidden induced subgraphs

Statement

Let $F$ be a nonempty family of graphs and let $ϵ \in (0, \frac{1}{2})$ . Then there exists $δ > 0$ such that every $F$ -free nonempty finite simple graph $G$ has an $ϵ$ -restricted vertex set of size at least $δ ∣ V (G) ∣$ .

Facts & Assumptions

Given: A nonempty family $F$ of graphs and a real $ϵ \in (0, \frac{1}{2})$ .

[L1]

A graph that is $F$ -free is $H$ -free for every $H \in F$ ( $H$ -free and $F$ -free graphs under the induced-subgraph convention).

[L2]

For every graph $H$ and $ϵ \in (0, 1 / 2)$ there is $δ > 0$ such that every nonempty $H$ -free graph $G$ has an $ϵ$ -restricted set of size at least $δ ∣ V (G) ∣$ (Rödl: for every $H$ and every $ϵ \in (0, \frac{1}{2})$ there is $δ > 0$ such that every nonempty $H$ -free graph has an $ϵ$ -restricted vertex set of size at least $δ ∣ V (G) ∣$ ).

Proof

technique · direct

1.1

Choose any graph $H \in F$ .

givenchoose

2.1

By [L2], there is a constant $δ > 0$ such that every nonempty $H$ -free graph has an $ϵ$ -restricted set of size at least $δ ∣ V (G) ∣$ .

step 1.1L2choose

3.1

If $G$ is nonempty and $F$ -free, then [L1] makes it $H$ -free, so step 2.1 applies to $G$ .

step 1.1step 2.1L1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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

Y. Huang, Q. Ju, and X. Zhou, Erdős-Hajnal beyond the five-vertex path, sec. 2 (standard reference, not scraped)