Alphabeta MathInduced Subgraphs and Hereditary Graph Classes
About this page
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.
✓ 14 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 14 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Real Analysis
2 · Logical flowchart
3 · Items
Definition
Induced embeddings and induced copies of a graph
Lemma
Induced embeddings compose, and the induced-subgraph relation is transitive up to isomorphism
Definition
The induced-embedding count ind_H(G)
Lemma
ind_H(G) is isomorphism-invariant and equals ind_H̄(Ḡ)
Definition
H-free and F-free graphs under the induced-subgraph convention
Lemma
Every induced subgraph of an F-free graph is F-free
Definition
Hereditary graph classes
Lemma
Every class defined by forbidden induced subgraphs is hereditary
Definition
Minimal forbidden induced subgraphs and forbidden bases
Theorem
Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs
Corollary
Every nonempty hereditary graph class contains the null graph
Definition
The complement of a graph class
Lemma
G[W]=Ḡ[W] for every vertex set W
Theorem
Complementation preserves hereditary classes and complements their minimal forbidden bases
Corollary
G is H-free if and only if Ḡ is H̄-free
Definition
Cliques, stable sets, the clique number ω(G) and stability number α(G)
Lemma
Complementation swaps cliques with stable sets, so ω(Ḡ)=α(G)
Definition
Anticonnected graphs and anticonnected components
Lemma
The anticonnected components of G are exactly the connected components of Ḡ
Theorem
Every graph with at least two vertices is connected or anticonnected
Definition
Edges between disjoint vertex sets; complete, anticomplete, pure and mixed pairs
Lemma
Purity is symmetric; complementation swaps complete and anticomplete pairs and preserves mixed pairs
Lemma