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
- Minimal forbidden induced subgraphs and forbidden bases Definition
- The complement of a graph class Definition
- Complete graphs form the hereditary class with forbidden basis {overline K₂} Example
- 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
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 8 results over 6 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)