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 hatted five-cycle and its complement have the Erdős-Hajnal property
Statement
Let be the graph obtained from a five-cycle by adding one vertex adjacent to two adjacent cycle vertices. Then the pair has the Erdős-Hajnal property.
Facts & Assumptions
Given: The graph .
Theorem 8.1 of the cited primary source proves exactly the Erdős-Hajnal property for , including the quantitative component-width and stable-pattern estimates.
Proof
The cited primary-source theorem constructs connected comb components of width at least , proves their pattern triangle-free, and extracts a stable pattern set of size at least .
The source chooses the critical exponent so those exact length and width bounds contradict criticality, thereby proving the stated Erdős-Hajnal property.
Depends on
- A hatted-five-cycle-free rooted stable-tooth comb yields a large pure blockade of components
- The star-expansion of $K_3$ contains the hatted five-cycle
- A tau-critical graph with a large low-degree induced subgraph has a rooted stable-tooth comb
- A tau-critical graph has no wide pure blockade with cograph pattern
- A minimal counterexample to a kappa-bound is tau-critical
- An H-free graph has a linearly large induced subgraph whose graph or complement has bounded maximum degree
- The Erdos-Hajnal property is equivalent to the large-cograph, large-perfect, and kappa formulations
- 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
43 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 8.1 (standard reference, not scraped)
- Shenwei Huang, Yiao Ju, and Yidong Zhou, Erdős-Hajnal beyond the five-vertex path, sentence after Theorem 1.9 (standard reference, not scraped)