AFTD Auto-Formalizing Theoretical Domains

card_simpleGraph

theoremverified

The number of simple graphs on a finite vertex set V is 2^{C(|V|,2)}, where C(|V|,2) = |V|(|V|-1)/2 is the number of unordered pairs of distinct vertices.

Statement

theorem card_simpleGraph {V : Type*} [Fintype V] [DecidableEq V] :
    Fintype.card (SimpleGraph V) = 2 ^ (Fintype.card V).choose 2
Source
folklore labelled-graph count; Mathlib has the number of edge labelings of the complete graph (card_topEdgeLabeling) and Sym2.card_subtype_not_diag, but not this count; supporting step for exists_cliqueFree_and_compl_cliqueFree.
Verified
10 Sep 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 7
  • k22_code_max_density_two_pow_geFor every natural number r ≥ 2, the maximum density of a K_{2,2}-code on Fin (2^r) is at least 1 / 2^r.
  • kst_code_linear_construction_finite_fieldLet n, s, t, r ≥ 1 be integers, and let w_1, ..., w_n in (ZMod 2)^r be vectors such that the sum of w_i over S is nonzero for every subset…
  • kst_code_max_density_antitoneFor all natural numbers s, t, n with 1 ≤ s and 1 ≤ t, the maximum density of a K_{s,t}-code is non-increasing in n: kst_code_max_density s…
  • ncard_even_edge_graphsFor every natural number n ≥ 2, the cardinality of the set of simple graphs on vertex set [n] having an even number of edges is 2^{n…
  • kst_code_card_leLet s, t, n be natural numbers with 1 ≤ s, 1 ≤ t, and s + t ≤ n. Every K_{s,t}-code C of simple graphs on vertex set [n] has cardinality…
  • k22_code_exists_dense_family_of_power_of_twoFor every natural number r ≥ 2, there exists a K_{2,2}-code on Fin (2^r) with density at least 1 / 2^r.
  • k22_code_card_leLet n be a natural number with 4 ≤ n. For every K_{2,2}-code C of simple graphs on Fin n, (n - 2) * Set.ncard C ≤ 2 ^ (n.choose 2).

Read back from the Lean

For every type V, assuming V is finite ([Fintype V]) and has decidable equality ([DecidableEq V]), the cardinality of the type SimpleGraph V — Mathlib's type of simple graphs with vertex set V — is equal to 2 raised to the binomial coefficient (Fintype.card V).choose 2. In words: if V has n vertices, there are exactly 2^(n choose 2) simple graphs on V. The equality is an equality of natural numbers.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The number of simple graphs on a finite vertex set V is 2^{C(|V|,2)}. -/theorem card_simpleGraph {V : Type*} [Fintype V] [DecidableEq V] :    Fintype.card (SimpleGraph V) = 2 ^ (Fintype.card V).choose 2 := by  have equiv : SimpleGraph V ≃ Set {e : Sym2 V // ¬ e.IsDiag} :=  { toFun := fun G => {e | (e : Sym2 V) ∈ G.edgeSet}    invFun := fun S => SimpleGraph.fromEdgeSet (Subtype.val '' S)    left_inv := by      intro G      have hS : (Subtype.val '' {e : {e : Sym2 V // ¬ e.IsDiag} | (e : Sym2 V) ∈ G.edgeSet})          = G.edgeSet := by        ext x        constructor        · rintro ⟨e, he, rfl⟩; exact he        · intro hx          exact ⟨⟨x, G.not_isDiag_of_mem_edgeSet hx⟩, hx, rfl⟩      simp only      rw [hS, SimpleGraph.fromEdgeSet_edgeSet]    right_inv := by      intro S      ext e      simp only [Set.mem_ofPred_eq]      constructor      · intro h        rw [SimpleGraph.edgeSet_fromEdgeSet, Set.mem_sdiff] at h        obtain ⟨h1, _⟩ := h        rcases h1 with ⟨e', he', hval⟩        have : e' = e := Subtype.ext hval        rw [this] at he'        exact he'      · intro he        rw [SimpleGraph.edgeSet_fromEdgeSet, Set.mem_sdiff]        refine ⟨?_, ?_⟩        · exact ⟨e, he, rfl⟩        · simpa [Sym2.mem_diagSet] using e.2 }  rw [Fintype.card_congr equiv, Fintype.card_set, Sym2.card_subtype_not_diag]
See it in the graphDiscuss this resultChallenge it