Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-08-01
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 C\mathcal C and every finite graph GG,

GCG is B(C)-free.G\in\mathcal C\quad\Longleftrightarrow\quad G\text{ is }\mathcal B(\mathcal C)\text{-free}.

If F\mathcal F is any forbidden induced-subgraph basis for C\mathcal C, then for every HB(C)H\in\mathcal B(\mathcal C), the family F\mathcal F contains a graph isomorphic to HH. Consequently, B(C)\mathcal B(\mathcal C) is, up to isomorphism, the unique inclusion-minimal forbidden basis for C\mathcal C.

Facts & Assumptions

Given: A hereditary class C\mathcal C and a finite graph GG.

[F1]

Membership in C\mathcal C passes to induced subgraphs and is invariant under graph isomorphism (Hereditary graph classes).

[F2]

B(C)\mathcal B(\mathcal C) consists exactly of graphs outside C\mathcal C all of whose proper induced subgraphs lie in C\mathcal C (Minimal forbidden induced subgraphs and forbidden bases).

[F3]

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 A\lvert A\rvert of a finite set, P(A)=2A\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert} for finite AA, The well-ordering principle).

[F4]

F\mathcal F-free means containing no induced member of F\mathcal F (HH-free and F\mathcal F-free graphs under the induced-subgraph convention).

Proof

technique · direct
1.1

If GCG\in\mathcal C, then no induced subgraph of GG lies outside C\mathcal C, so in particular GG contains no member of B(C)\mathcal B(\mathcal C).

F1F2
1.2

Suppose GCG\notin\mathcal C. Among vertex sets WV(G)W\subseteq V(G) for which G[W]CG[W]\notin\mathcal C, choose one of least cardinality; it exists because W=V(G)W=V(G) is available.

chooseF3
1.3

Let F\mathcal F be any forbidden induced-subgraph basis for C\mathcal C. Every JFJ\in\mathcal F lies outside C\mathcal C: otherwise JCJ\in\mathcal C would contain itself as an induced copy of a member of F\mathcal F, contradicting the defining equivalence for F\mathcal F.

F4
2.1

Every proper induced subgraph of G[W]G[W] lies in C\mathcal C by minimality of W|W|. Hence G[W]B(C)G[W]\in\mathcal B(\mathcal C).

step 1.2F2
2.2

Fix HB(C)H\in\mathcal B(\mathcal C). Since HCH\notin\mathcal C, it is not F\mathcal F-free, so some JFJ\in\mathcal F occurs as an induced subgraph of HH. If that copy were proper, then it would lie in C\mathcal C by the minimality of HH; closure under isomorphism would give JCJ\in\mathcal C, contradicting step 1.3. Thus the copy uses all vertices of HH, and JHJ\cong H.

F1F2F4step 1.3
3.1

Thus GG is not B(C)\mathcal B(\mathcal C)-free. Together with step 1.1 this proves the equivalence.

step 2.1step 1.1F4
4.1

Hence every forbidden basis for C\mathcal C contains, up to isomorphism, every member of B(C)\mathcal B(\mathcal C). Since B(C)\mathcal B(\mathcal C) 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.

step 3.1step 2.2

Depends on

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