Alphabeta Math
CorollaryStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-07-31
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.

There are 2(n2)2^{\binom{n}{2}} simple graphs on a fixed labelled nn-element vertex set

Statement

On a fixed labelled nn-element vertex set VV, there are exactly 2(n2)2^{\binom n2} finite simple graphs.

Facts & Assumptions

Given: A fixed finite set VV with ∣V∣=n|V|=n.

[F1]

A simple graph on VV is uniquely specified by choosing an edge set E⊆[V]2E\subseteq[V]^2 (A finite simple graph is a finite vertex set together with a set of two-element vertex subsets).

[L1]

The set [V]2[V]^2 has (n2)\binom n2 elements (A finite set with nn elements has exactly (n2)\binom{n}{2} two-element subsets, and 2(n2)=n(n−1)2\binom{n}{2} = n(n-1)).

[L2]

A finite set with mm elements has a power set with 2m2^m elements (∣P(A)∣=2∣A∣\lvert\mathcal{P}(A)\rvert = 2^{\lvert A\rvert} for finite AA).

Proof

technique · direct
1.1

Sending a graph (V,E)(V,E) to its edge set is a bijection from the simple graphs on the fixed labelled set VV to the power set P([V]2)\mathcal P([V]^2), by [F1].

F1
2.1

By [L1] and [L2], ∣P([V]2)∣=2∣[V]2∣=2(n2)|\mathcal P([V]^2)|=2^{|[V]^2|}=2^{\binom n2}. Combining with step 1.1 gives the stated count.

step 1.1L1L2∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 60 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