Alphabeta MathDefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-5.6-terra)audited 2026-09-01
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.
The graphs
Definition
Let be the graph on vertices
whose edge set is
Thus is the five-wheel with hub and rim cycle .
For each , define recursively from by adjoining a new leaf adjacent only to . In particular, adds a leaf at , and adds one leaf at every rim vertex of the five-wheel.
Used by
- The graph H₀ has the Erdős-Hajnal property Corollary
- The H₅-overlap-chain relation in one comb block Definition
- An H₅-overlap class and its terminal quotient Example
- H₀ is the five-wheel Example
- H₁ and H₅ arise by the stated labelled leaf attachments Example
- Every H₅-overlap class is connected Lemma
- In a special-vertex comb of a co-E-free graph, vertices in other comb blocks remain pure to every H₅-overlap quotient block Lemma
- Relative to a complete nonedge pair in a co-E-free graph, every one-sided vertex is pure to an induced H₅ Lemma
- The family consisting of H₅ and co-E has the Erdős–Hajnal property Lemma
- The pattern of the terminal H₅-overlap quotient is {H₅,co-E}-free Lemma
- A special-vertex comb in a co-E-free graph admits the {H₅,co-E} structural partition Theorem
Dependency tree · 0 levels
Nothing. This result depends on no other item in the library.
Sources
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, Figure 7 (standard reference, not scraped)