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.
Every class defined by forbidden induced subgraphs is hereditary
Statement
For every family of finite graphs, the class of all -free finite graphs is hereditary.
Facts & Assumptions
Given: A family of finite graphs.
Induced subgraphs of an -free graph remain -free (Every induced subgraph of an -free graph is -free).
-freeness is invariant under graph isomorphism (-free and -free graphs under the induced-subgraph convention).
Heredity means closure under isomorphism and induced subgraphs (Hereditary graph classes).
Proof
The class of -free graphs is closed under isomorphism because an isomorphism transports every induced copy in both directions.
It is closed under induced subgraphs by L1.
These are exactly the two requirements for a hereditary class.
Depends on
Used by
- Every graph on at most three vertices has the Erdős–Hajnal property Corollary
- For every forest H, graphs excluding H and H̄ have the Erdős-Hajnal property Corollary
- For every λ>0 a bounded number of disjoint ε-restricted sets covers all but λ|V(G)| vertices of an H-free graph Corollary
- Substituting a complete or an edgeless graph for a vertex preserves the Erdős–Hajnal property Corollary
- Forbidding P₃ and forbidding P₃ have the same Erdős–Hajnal constants Example
- The leaf/co-leaf corollary recovers the P₅ case from the P₄ case Example
- If ε is an Erdős–Hajnal constant for H and W is a nonempty vertex set with |W|^ε>hom(G), then G[W] has an induced copy of H Lemma
- If H is an induced subgraph of H' and H' has the Erdős–Hajnal property, then H has it with every constant of H' Proposition
- Alon–Pach–Solymosi: if H₁ and H₂ have the Erdős–Hajnal property, so does the graph obtained from H₁ by substituting H₂ for a vertex Theorem
- Every H-free graph partitions into boundedly many vertex sets of self-density at most ε or at least 1-ε Theorem
- Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs Theorem
- Every P₃-free graph G satisfies hom(G)≥√|V(G)| Theorem
- For every forest H, graphs excluding H and H̄ have a linear pure pair Theorem
- For every t≥1, the class of Kₜ-free graphs has the Erdős–Hajnal property Theorem
- The Bird graph has the Erdős-Hajnal property Theorem
- The E-graph has the Erdős-Hajnal property Theorem
- The single-forbidden-graph and finite-nonempty-family formulations of the Erdős–Hajnal conjecture are equivalent Theorem
Dependency tree · two levels
7 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
- Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)