Alphabeta MathHow 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 five-vertex path is leaf-reducible
Example
The singleton family is leaf-reducible.
Facts & Assumptions
Given: The path graph .
A family is leaf-reducible if deleting one leaf from one member leaves a modified family with the Erdős-Hajnal property (Leaf-reducible finite graph families).
Every -free graph has a clique or stable set of size at least the square root of its order (Every -free graph has a clique or stable set of size at least the square root of its order).
A graph has the Erdős-Hajnal property when its forbidden induced-subgraph class has some positive exponent (The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class).
Verification
An endpoint of is a leaf, and deleting it leaves the four-vertex path .
By [L2], the class of -free graphs has the positive exponent , so [L3] says that has the Erdős-Hajnal property. Therefore the modified singleton family satisfies the condition in [L1].
Hence the singleton family is leaf-reducible.
Depends on
- Leaf-reducible finite graph families
- Every $P_4$-free graph has a clique or stable set of size at least the square root of its order
- The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class
- 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
18 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
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, definition of leaf-reducible (standard reference, not scraped)
- Tung H. Nguyen, Notes on Recent Work on the Erdős-Hajnal Conjecture, Exercise 1.1 (standard reference, not scraped)