Alphabeta Math
DefinitionDefinition: AI-adaptedProof: Not applicableSession-authored (Fable 5 assisted)audited 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.

Cliques, stable sets, the clique number ω(G)\omega(G) and stability number α(G)\alpha(G)

Definition

Let GG be a finite simple graph. A set XV(G)X\subseteq V(G) is a clique when every two distinct vertices of XX are adjacent, equivalently when G[X]G[X] is complete. It is a stable set, or independent set, when no two distinct vertices of XX are adjacent, equivalently when G[X]G[X] is edgeless (Subgraphs, induced subgraphs and spanning subgraphs, Empty and complete graphs, complete bipartite graphs, and the convention that PnP_n and CnC_n have nn vertices).

The clique number and stability number are

ω(G):=max{X:X is a clique in G},α(G):=max{X:X is a stable set in G}.\omega(G):=\max\{|X|:X\text{ is a clique in }G\},\qquad \alpha(G):=\max\{|X|:X\text{ is a stable set in }G\}.

Both maxima exist because the families are nonempty, containing \varnothing, and lie inside the finite power set of V(G)V(G) (The cardinality A\lvert A\rvert of a finite set, P(A)=2A\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert} for finite AA, A subset of a finite set is finite, with BA\lvert B\rvert \le \lvert A\rvert, and equality holds if and only if B=AB = A, The well-ordering principle). In particular, ω(K0)=α(K0)=0\omega(K_0)=\alpha(K_0)=0.

Depends on

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