Alphabeta Math
False statementConstruction: AI-adaptedVerification: 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 has a finite forbidden induced-subgraph basis

False Statement

Every hereditary graph class has a finite minimal forbidden induced-subgraph basis.

Facts & Assumptions

Given: The hereditary class B of finite bipartite graphs.

[L1]

A graph is bipartite if and only if it contains no odd cycle (A bipartite graph and a proper two-colouring of its vertices, A finite graph is bipartite if and only if it has no odd cycle).

[F1]

For every k≥1, C2k+1 is an odd cycle, and distinct lengths give nonisomorphic graphs (Empty and complete graphs, complete bipartite graphs, and the convention that Pn and Cn have n vertices).

[F2]

A minimal forbidden induced subgraph is outside the class while all proper induced subgraphs are inside (Minimal forbidden induced subgraphs and forbidden bases).

[L2]

The family of all such minimal graphs is the unique minimal basis (Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs).

Refutation

technique · contradiction
1.1

Suppose the minimal forbidden basis of B is finite.

assume-contra
1.2

For every k≥1, the graph C2k+1 is not bipartite. Every proper induced subgraph of this chordless cycle is a disjoint union of paths, hence is bipartite. Thus C2k+1 is minimally forbidden.

L1F1F2
2.1

The minimal basis therefore contains the pairwise nonisomorphic graphs C3,C5,C7,….

step 1.2L2
3.1

This is an infinite family, contradicting step 1.1. Hence a hereditary class need not have a finite minimal forbidden basis.

step 1.1step 2.1discharge-contradiction∎

Remarks


% C_5. \node[vertex] (b1) at (3.2,1.3) {}; \node[vertex] (b2) at (4.35,.35) {}; \node[vertex] (b3) at (3.9,-1.0) {}; \node[vertex] (b4) at (2.5,-1.0) {}; \node[vertex] (b5) at (2.05,.35) {}; \draw[edge] (b1)--(b2)--(b3)--(b4)--(b5)--cycle; \node[caption] at (3.2,-1.55) {$C_5$};

% C_7. \node[vertex] (c1) at (6.7,1.35) {}; \node[vertex] (c2) at (7.8,.85) {}; \node[vertex] (c3) at (8.05,-.35) {}; \node[vertex] (c4) at (7.3,-1.3) {}; \node[vertex] (c5) at (6.1,-1.3) {}; \node[vertex] (c6) at (5.35,-.35) {}; \node[vertex] (c7) at (5.6,.85) {}; \draw[edge] (c1)--(c2)--(c3)--(c4)--(c5)--(c6)--(c7)--cycle; \node[caption] at (6.7,-1.85) {$C_7$};

\node[font=\Large] at (9.2,0) {$\cdots$}; \node[caption] at (4.6,-2.45) {$C_3,C_5,C_7,\ldots$ are the pairwise nonisomorphic minimal forbidden graphs}; \end{tikzpicture} ```

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

21 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