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.

Complementation preserves hereditary classes and complements their minimal forbidden bases

Statement

If $\mathcal C$ is hereditary, then $\overline{\mathcal C}$ is hereditary and

$\mathcal B(\overline{\mathcal C})=\{\overline H:H\in\mathcal B(\mathcal C)\}$

up to isomorphism.

Facts & Assumptions

Given: A hereditary graph class $\mathcal C$ .

[F1]

$G\in\overline{\mathcal C}$ exactly when $\overline G\in\mathcal C$ (The complement of a graph class).

[L1]

Complementation commutes with taking induced subgraphs ( $\overline{G[W]}=\overline G[W]$ for every vertex set $W$ ).

[F2]

A minimal forbidden graph lies outside the class while all its proper induced subgraphs lie inside (Minimal forbidden induced subgraphs and forbidden bases).

[L2]

A hereditary class is determined by its unique minimal forbidden basis (Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs).

Proof

technique · direct

1.1

Let $G\in\overline{\mathcal C}$ and $W\subseteq V(G)$ . Then $\overline G\in\mathcal C$ , so $\overline G[W]\in\mathcal C$ by heredity.

1.2

Let $H\in\mathcal B(\mathcal C)$ . Then $\overline H\notin\overline{\mathcal C}$ , while for every proper $W\subsetneq V(H)$ , $H[W]\in\mathcal C$ and therefore $\overline H[W]=\overline{H[W]}\in\overline{\mathcal C}$ .

F1F2L1

2.1

Since $\overline{G[W]}=\overline G[W]$ , one has $G[W]\in\overline{\mathcal C}$ . Isomorphism closure is likewise preserved, so $\overline{\mathcal C}$ is hereditary.

step 1.1L1F1

2.2

Hence $\overline H\in\mathcal B(\overline{\mathcal C})$ . Applying the same argument to the involution of complementation gives the reverse inclusion.

step 1.2F2

3.1

Therefore the minimal bases are complementary as claimed.

step 2.2L2∎

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 32 results over 16 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)
ISGCI, Self-complementary classes (standard reference, not scraped)