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.
Hereditary graph classes
Definition
A class of finite simple graphs is a hereditary graph class when:
- it is closed under isomorphism; and
- whenever and has an induced embedding into , one has .
The second clause is closure under taking induced subgraphs (Induced embeddings and induced copies of a graph). Isomorphism closure makes membership depend only on graph structure, not on the chosen vertex labels (Graph isomorphisms, automorphisms and graph complements).
Depends on
Used by
- Every nonempty hereditary graph class contains the null graph Corollary
- The class of connected graphs is not hereditary Counterexample
- The class of regular graphs is not hereditary Counterexample
- Graph edit distance and being ε-far from an induced-hereditary property Definition
- Minimal forbidden induced subgraphs and forbidden bases Definition
- The complement of a graph class Definition
- The Erdős–Hajnal property and an Erdős–Hajnal constant for a hereditary graph class Definition
- The strong Erdős–Hajnal property for a hereditary graph class Definition
- Complete graphs form the hereditary class with forbidden basis {K̄₂} Example
- Every hereditary graph class has the Erdős–Hajnal property False statement
- Every hereditary graph class is closed under taking arbitrary subgraphs False statement
- Every class defined by forbidden induced subgraphs is hereditary Lemma
- Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs Theorem
- The strong Erdős–Hajnal property implies the Erdős–Hajnal property Theorem
Dependency tree · two levels
5 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)