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 cycle of length at least five and a forest complement have the Erdős-Hajnal property
Statement
Let be a cycle of length at least and let be a forest. Then the pair has the Erdős-Hajnal property.
Facts & Assumptions
Given: A cycle of length and a forest .
For every forest , the pair has the Erdős-Hajnal property (A forest complement and its star-expansion have the Erdős-Hajnal property).
If a forest contains a path of length , then its star-expansion contains an induced -cycle (A star-expansion of a forest containing a long path contains the corresponding cycle).
The Erdős-Hajnal property passes to hereditary subclasses (The Erdős–Hajnal property and each of its constants pass to hereditary subclasses).
Proof
Choose a forest that contains as an induced subgraph and also contains an induced path on vertices. For instance, take the disjoint union of with a path long enough to realize that length. By [L2], the star-expansion contains an induced copy of .
If a graph is -free and -free, then it is also -free and -free. Indeed, an induced copy of would contain the induced cycle from step 1.1, and an induced copy of would contain because is an induced subgraph of . Thus the class forbidding is a hereditary subclass of the class forbidding .
By [L1], the larger class from step 2.1 has the Erdős-Hajnal property, so [L3] passes that property to the subclass forbidding .
Depends on
- A forest complement and its star-expansion have the Erdős-Hajnal property
- A star-expansion of a forest containing a long path contains the corresponding cycle
- The Erdős–Hajnal property and each of its constants pass to hereditary subclasses
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
19 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 1.9 (standard reference, not scraped)