Alphabeta MathHow 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.
-free and -free graphs under the induced-subgraph convention
Definition
For finite graphs and , the graph is -free when has no induced copy of (Induced embeddings and induced copies of a graph). Equivalently,
(The induced-embedding count ).
For a family of finite graphs, a finite graph is -free when it is -free for every . Throughout this page, “free” always refers to induced subgraphs. It does not merely prohibit ordinary subgraph copies.
Depends on
Used by
- G is H-free if and only if overline G is overline H-free Corollary
- Minimal forbidden induced subgraphs and forbidden bases Definition
- A graph is P₃-free if and only if every connected component is complete Example
- Every class defined by forbidden induced subgraphs is hereditary Lemma
- Every induced subgraph of an mathcal F-free graph is mathcal F-free Lemma
- Every hereditary graph class is determined by its unique minimal forbidden induced subgraphs Theorem
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 26 results over 13 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)