How 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 hereditary graph class is determined by its unique minimal forbidden induced subgraphs
Statement
For every hereditary graph class and every finite graph ,
If is any forbidden induced-subgraph basis for , then for every , the family contains a graph isomorphic to . Consequently, is, up to isomorphism, the unique inclusion-minimal forbidden basis for .
Facts & Assumptions
Given: A hereditary class and a finite graph .
Membership in passes to induced subgraphs and is invariant under graph isomorphism (Hereditary graph classes).
consists exactly of graphs outside all of whose proper induced subgraphs lie in (Minimal forbidden induced subgraphs and forbidden bases).
A finite vertex set has finitely many subsets, whose cardinalities are natural numbers; every nonempty set of natural numbers has a least element (The cardinality of a finite set, for finite , The well-ordering principle).
-free means containing no induced member of (-free and -free graphs under the induced-subgraph convention).
Proof
If , then no induced subgraph of lies outside , so in particular contains no member of .
Suppose . Among vertex sets for which , choose one of least cardinality; it exists because is available.
Let be any forbidden induced-subgraph basis for . Every lies outside : otherwise would contain itself as an induced copy of a member of , contradicting the defining equivalence for .
Every proper induced subgraph of lies in by minimality of . Hence .
Fix . Since , it is not -free, so some occurs as an induced subgraph of . If that copy were proper, then it would lie in by the minimality of ; closure under isomorphism would give , contradicting step 1.3. Thus the copy uses all vertices of , and .
Thus is not -free. Together with step 1.1 this proves the equivalence.
Hence every forbidden basis for contains, up to isomorphism, every member of . Since is itself a basis by step 3.1, it is inclusion-minimal, and any inclusion-minimal forbidden basis has no additional members. This proves uniqueness up to isomorphism.
Depends on
- Minimal forbidden induced subgraphs and forbidden bases
- Hereditary graph classes
- $H$-free and $\mathcal F$-free graphs under the induced-subgraph convention
- Every class defined by forbidden induced subgraphs is hereditary
- The cardinality $\lvert A\rvert$ of a finite set
- $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$
- The well-ordering principle
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 57 results over 22 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)