Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-generatedprecheck 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 and every finite graph G,

G∈C⟺G is B(C)-free.

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

Facts & Assumptions

Given: A hereditary class C and a finite graph G.

[F1]

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

[F2]

B(C) consists exactly of graphs outside C all of whose proper induced subgraphs lie in 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∣ of a finite set, ∣P(A)∣=2∣A∣ for finite A, The well-ordering principle).

[F4]

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

Proof

technique · direct
1.1

If G∈C, then no induced subgraph of G lies outside C, so in particular G contains no member of B(C).

F1F2
1.2

Suppose G∉C. Among vertex sets W⊆V(G) for which G[W]∉C, choose one of least cardinality; it exists because W=V(G) is available.

chooseF3
1.3

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

F4
2.1

Every proper induced subgraph of G[W] lies in C by minimality of ∣W∣. Hence G[W]∈B(C).

step 1.2F2
2.2

Fix H∈B(C). Since H∉C, it is not F-free, so some J∈F occurs as an induced subgraph of H. If that copy were proper, then it would lie in C by the minimality of H; closure under isomorphism would give J∈C, contradicting step 1.3. Thus the copy uses all vertices of H, and J≅H.

F1F2F4step 1.3
3.1

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

step 2.1step 1.1F4
4.1

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

28 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