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.
Cliques, stable sets, the clique number and stability number
Definition
Let be a finite simple graph. A set is a clique when every two distinct vertices of are adjacent, equivalently when is complete. It is a stable set, or independent set, when no two distinct vertices of are adjacent, equivalently when is edgeless (Subgraphs, induced subgraphs and spanning subgraphs, Empty and complete graphs, complete bipartite graphs, and the convention that and have vertices).
The clique number and stability number are
Both maxima exist because the families are nonempty, containing , and lie inside the finite power set of (The cardinality of a finite set, for finite , A subset of a finite set is finite, with , and equality holds if and only if , The well-ordering principle). In particular, .
Depends on
- A finite simple graph is a finite vertex set together with a set of two-element vertex subsets
- Subgraphs, induced subgraphs and spanning subgraphs
- Empty and complete graphs, complete bipartite graphs, and the convention that $P_n$ and $C_n$ have $n$ vertices
- The cardinality $\lvert A\rvert$ of a finite set
- $\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert}$ for finite $A$
- A subset of a finite set is finite, with $\lvert B\rvert \le \lvert A\rvert$, and equality holds if and only if $B = A$
- The well-ordering principle
Used by
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 55 results over 21 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
- Reinhard Diestel, Graph Theory, Preview Chapter 1 (standard reference, not scraped)
- Valerio Boncompagni, On hereditary graph classes defined by forbidding Truemper configurations (PhD thesis, 2018) (standard reference, not scraped)