CorollaryStatement: AI-adaptedProof: AI-generatedprecheck 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^{(\binom{n}{2})}$ simple graphs on a fixed labelled $n$ -element vertex set

Statement

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

Facts & Assumptions

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

[F1]

A simple graph on $V$ is uniquely specified by choosing an edge set $E \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}$ has $(\binom{n}{2})$ elements (A finite set with $n$ elements has exactly $(\binom{n}{2})$ two-element subsets, and $2 (\binom{n}{2}) = n (n - 1)$ ).

[L2]

A finite set with $m$ elements has a power set with $2^{m}$ elements ( $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ ).

Proof

technique · direct

1.1

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

2.1

By [L1] and [L2], $∣ P ([V]^{2}) ∣ = 2^{∣ [V]^{2} ∣} = 2^{(\binom{n}{2})}$ . 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 · two levels

23 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

R. Diestel, Graph Theory, Chapter 1 preview (standard reference, not scraped)

There are 2(n2)2(2n​) simple graphs on a fixed labelled nn-element vertex set