AFTD Auto-Formalizing Theoretical Domains

ncard_even_edge_graphs

theoremverified

For 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 choose 2 - 1}.

Statement

theorem ncard_even_edge_graphs (n : ℕ) (hn : 2 ≤ n) :
    Set.ncard (open Classical in {G : SimpleGraph (Fin n) | Even G.edgeFinset.card}) = 2 ^ (n.choose 2 - 1)
Source
arXiv:2610.35136, Sharp Bounds for Graph-Codes Avoiding Complete Bipartite Differences, Proposition 3.2
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • card_simpleGraphThe 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…
Used by 1
  • kst_code_density_odd_oddLet s and t be odd natural numbers, and let n be a natural number such that s + t ≤ n. Then the maximum density of a K_{s,t}-code in…

Read back from the Lean

For any natural number $n$ such that $n \ge 2$, the number of simple graphs with vertex set $\{0, 1, \dots, n-1\}$ (i.e., Fin n) whose edge set has an even number of edges is equal to $2^{\binom{n}{2} - 1}$ (evaluated using Set.ncard).

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

The proof, explained

To count the simple graphs on n vertices (n ≥ 2) having an even number of edges, we fix a non-loop edge e = {0, 1}. Toggling the presence of e defines an involution on the set of simple graphs that strictly inverts the parity of the edge count, establishing a bijection between the set S of even-edge graphs and its complement Sᶜ of odd-edge graphs. Since the total number of simple graphs on n vertices is |S| + |Sᶜ| = 2^{n choose 2} and |S| = |Sᶜ|, we have 2|S| = 2^{n choose 2}, whence |S| = 2^{n choose 2 - 1}.

  1. For any non-loop edge e, toggling e in a simple graph G produces a graph whose edge set is the symmetric difference of G's edge set and {e}.

    The toggled graph `ncard_even_edge_graphs_flip e G` is defined by constructing a simple graph from the symmetric difference of E(G) and {e}. By `SimpleGraph.edgeSet_fromEdgeSet`, its edge set consists of all elements of that symmetric difference with diagonal elements (self-loops) removed. By extensionality, an edge x belongs to the resulting graph if and only if x is in the symmetric difference and is not diagonal. In the forward direction, membership in the difference implies membership in the symmetric difference. In the reverse direction, if x is in the symmetric difference, it is either an edge of G (hence not diagonal since G is a simple graph) or it is e (not diagonal by hypothesis `he`). Thus no element of the symmetric difference is diagonal, and the edge set is exactly E(G) Δ {e}.

    lines 1–20

    uses SimpleGraph.edgeSet_fromEdgeSet, Set.mem_sdiff, Set.mem_symmDiff, Set.mem_singleton_iff, Sym2.mem_diagSet

    /-- Toggle the edge `e` in the graph `G`. -/
    private def ncard_even_edge_graphs_flip {n : ℕ} (e : Sym2 (Fin n)) (G : SimpleGraph (Fin n)) :
        SimpleGraph (Fin n) :=
      SimpleGraph.fromEdgeSet (symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))))
    
    /-- The edge set of the toggled graph is the symmetric difference of edge sets. -/
    private theorem ncard_even_edge_graphs_flip_edgeSet {n : ℕ} (e : Sym2 (Fin n)) (he : ¬ e.IsDiag)
        (G : SimpleGraph (Fin n)) :
        (ncard_even_edge_graphs_flip e G).edgeSet = symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))) := by
      simp only [ncard_even_edge_graphs_flip, SimpleGraph.edgeSet_fromEdgeSet]
      ext x
      simp only [Set.mem_sdiff, Set.mem_symmDiff, Set.mem_singleton_iff, Sym2.mem_diagSet]
      constructor
      · rintro ⟨h, -⟩; exact h
      · intro h
        refine ⟨h, ?_⟩
        rcases h with ⟨hxG, hxe⟩ | ⟨hxe, hxG⟩
        · exact G.not_isDiag_of_mem_edgeSet hxG
        · subst hxe; exact he
    
  2. Toggling the same non-loop edge e twice is the identity on simple graphs.

    Two simple graphs are equal if and only if their edge sets are equal (by `SimpleGraph.edgeSet_inj.mp`). Rewriting both toggles using `ncard_even_edge_graphs_flip_edgeSet` expresses the resulting edge set as (E(G) Δ {e}) Δ {e}. By `symmDiff_symmDiff_cancel_right`, taking the symmetric difference with {e} twice cancels out, restoring E(G).

    lines 21–29

    uses SimpleGraph.edgeSet_inj.mp, ncard_even_edge_graphs_flip_edgeSet, symmDiff_symmDiff_cancel_right

    /-- Toggling the same non-loop edge twice is the identity. -/
    private theorem ncard_even_edge_graphs_flip_involutive {n : ℕ} (e : Sym2 (Fin n))
        (he : ¬ e.IsDiag) (G : SimpleGraph (Fin n)) :
        ncard_even_edge_graphs_flip e (ncard_even_edge_graphs_flip e G) = G := by
      apply SimpleGraph.edgeSet_inj.mp
      rw [ncard_even_edge_graphs_flip_edgeSet e he (ncard_even_edge_graphs_flip e G),
        ncard_even_edge_graphs_flip_edgeSet e he G]
      exact symmDiff_symmDiff_cancel_right ({e} : Set (Sym2 (Fin n))) G.edgeSet
    
  3. If the non-loop edge e is already present in G, toggling e changes the parity of the edge count.

    When e ∈ E(G), the singleton {e} is a subset of E(G) (`Set.singleton_subset_iff.mpr`), so E(G) Δ {e} reduces to E(G) \ {e}. Its cardinality is |E(G)| - 1 by `Set.ncard_sdiff` and `Set.ncard_singleton`. Since e ∈ E(G), E(G) is nonempty, so |E(G)| ≥ 1 (`Set.ncard_pos`, `omega`). By `Nat.even_sub`, |E(G)| - 1 is even if and only if |E(G)| and 1 have the same parity, which means |E(G)| - 1 is even if and only if |E(G)| is odd.

    lines 30–47

    uses ncard_even_edge_graphs_flip_edgeSet, Set.singleton_subset_iff.mpr, Set.symmDiff_def, Set.sdiff_eq_empty.mpr, Set.union_empty, Set.ncard_sdiff, Set.ncard_singleton, Set.ncard_pos, Nat.even_sub

    /-- Toggling a non-loop edge flips the parity of the number of edges. -/
    private theorem ncard_even_edge_graphs_flip_ncard_even {n : ℕ} (e : Sym2 (Fin n))
        (he : ¬ e.IsDiag) (G : SimpleGraph (Fin n)) :
        Even (ncard_even_edge_graphs_flip e G).edgeSet.ncard ↔ ¬ Even G.edgeSet.ncard := by
      classical
      rw [ncard_even_edge_graphs_flip_edgeSet e he G]
      by_cases hmem : e ∈ G.edgeSet
      · have hsub : ({e} : Set (Sym2 (Fin n))) ⊆ G.edgeSet := Set.singleton_subset_iff.mpr hmem
        have hset : symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))) = G.edgeSet \ {e} := by
          rw [Set.symmDiff_def, Set.sdiff_eq_empty.mpr hsub, Set.union_empty]
        rw [hset, Set.ncard_sdiff hsub, Set.ncard_singleton]
        have hpos : 1 ≤ G.edgeSet.ncard := by
          have h0 : 0 < G.edgeSet.ncard := by
            rw [Set.ncard_pos]
            exact ⟨e, hmem⟩
          omega
        rw [Nat.even_sub hpos]
        simp
  4. If the non-loop edge e is not in G, toggling e changes the parity of the edge count.

    When e ∉ E(G), the symmetric difference E(G) Δ {e} equals E(G) ∪ {e} (`insert e G.edgeSet`). Since e ∉ E(G), the cardinality of the new edge set is |E(G)| + 1 by `Set.ncard_insert_of_notMem`. By `Nat.even_add_one`, |E(G)| + 1 is even if and only if |E(G)| is odd. Together with the previous case, this proves toggling e always inverts the parity of the edge count.

    lines 48–59

    uses Set.mem_symmDiff, Set.mem_singleton_iff, Set.mem_insert_iff, Or.inr, Or.inl, Set.ncard_insert_of_notMem, Nat.even_add_one

      · have hset : symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))) = insert e G.edgeSet := by
          ext x
          simp only [Set.mem_symmDiff, Set.mem_singleton_iff, Set.mem_insert_iff]
          constructor
          · rintro (⟨hx, -⟩ | ⟨rfl, -⟩)
            · exact Or.inr hx
            · exact Or.inl rfl
          · rintro (rfl | hx)
            · exact Or.inr ⟨rfl, hmem⟩
            · exact Or.inl ⟨hx, fun hxe => hmem (hxe ▸ hx)⟩
        rw [hset, Set.ncard_insert_of_notMem hmem, Nat.even_add_one]
    
  5. The parity of a simple graph's edge count as a finite set equals the parity of its edge count as a set.

    Rewriting with `SimpleGraph.edgeFinset_card`, `Set.ncard_eq_toFinset_card'`, and `Set.toFinset_card` shows that the finset cardinality `G.edgeFinset.card` and the set cardinality `G.edgeSet.ncard` both equal the type-theoretic cardinality of the edge set as a finite type. Hence their parities coincide.

    lines 60–65

    uses SimpleGraph.edgeFinset_card, Set.ncard_eq_toFinset_card', Set.toFinset_card

    /-- The parity of the number of edges equals the parity of the edge-set cardinality. -/
    private theorem ncard_even_edge_graphs_even_iff {n : ℕ} (G : SimpleGraph (Fin n)) :
        (open Classical in Even G.edgeFinset.card ↔ Even G.edgeSet.ncard) := by
      classical
      rw [SimpleGraph.edgeFinset_card, Set.ncard_eq_toFinset_card', Set.toFinset_card]
    
  6. Toggling a non-loop edge flips the parity of the graph's finset edge count.

    By converting the parity of the finset edge count to the parity of the set edge count using `ncard_even_edge_graphs_even_iff`, the result follows immediately from `ncard_even_edge_graphs_flip_ncard_even`.

    lines 66–73

    uses ncard_even_edge_graphs_even_iff, ncard_even_edge_graphs_flip_ncard_even

    /-- Toggling a non-loop edge flips the parity of the edge count. -/
    private theorem ncard_even_edge_graphs_flip_even {n : ℕ} (e : Sym2 (Fin n))
        (he : ¬ e.IsDiag) (G : SimpleGraph (Fin n)) :
        (open Classical in
          Even (ncard_even_edge_graphs_flip e G).edgeFinset.card ↔ ¬ Even G.edgeFinset.card) := by
      rw [ncard_even_edge_graphs_even_iff, ncard_even_edge_graphs_even_iff,
        ncard_even_edge_graphs_flip_ncard_even e he G]
    
  7. For n ≥ 2, the pair e = {0, 1} is a valid non-loop edge on vertex set Fin n.

    Because n ≥ 2, 0 and 1 are valid distinct indices in Fin n. By `Sym2.mk_isDiag_iff`, e is a diagonal element if and only if 0 = 1 in Fin n. Applying `congrArg Fin.val` would imply 0 = 1 in ℕ, which is impossible (`omega`), confirming e is not a self-loop.

    lines 74–83

    uses Sym2.mk_isDiag_iff, congrArg, Fin.val

    /-- Exactly half of all simple graphs on Fin n have an even number of edges for n ≥ 2. -/
    theorem ncard_even_edge_graphs (n : ℕ) (hn : 2 ≤ n) :
        Set.ncard (open Classical in {G : SimpleGraph (Fin n) | Even G.edgeFinset.card}) = 2 ^ (n.choose 2 - 1) := by
      classical
      set e : Sym2 (Fin n) := s(⟨0, by omega⟩, ⟨1, by omega⟩)
      have he : ¬ e.IsDiag := by
        rw [Sym2.mk_isDiag_iff]
        intro h
        have h2 : (0 : ℕ) = 1 := congrArg Fin.val h
        omega
  8. The set S of graphs with an even number of edges has the same cardinality as its complement Sᶜ.

    Let S = {G | Even |E(G)|}. By `Set.ncard_congr`, |S| = |Sᶜ| if toggling e defines a bijection from S to Sᶜ. First, toggling e maps any G ∈ S to Sᶜ by `ncard_even_edge_graphs_flip_even`. Second, this map is injective because toggling is involutive (`ncard_even_edge_graphs_flip_involutive`). Third, it is surjective because for any G ∈ Sᶜ, toggling G gives a graph in S that maps back to G.

    lines 84–99

    uses Set.ncard_congr, ncard_even_edge_graphs_flip_even, ncard_even_edge_graphs_flip_involutive

      set S : Set (SimpleGraph (Fin n)) := {G | Even G.edgeFinset.card} with hS
      have hcongr : S.ncard = Sᶜ.ncard := by
        refine Set.ncard_congr (fun G _ => ncard_even_edge_graphs_flip e G) ?_ ?_ ?_
        · intro G hG
          simp only [hS, Set.mem_ofPred_eq] at hG
          simp only [Set.mem_compl_iff, hS, Set.mem_ofPred_eq]
          exact fun h => (ncard_even_edge_graphs_flip_even e he G).mp h hG
        · intro G₁ G₂ _ _ h
          rw [← ncard_even_edge_graphs_flip_involutive e he G₁,
            ← ncard_even_edge_graphs_flip_involutive e he G₂, h]
        · intro G hG
          simp only [Set.mem_compl_iff, hS, Set.mem_ofPred_eq] at hG
          refine ⟨ncard_even_edge_graphs_flip e G, ?_,
            ncard_even_edge_graphs_flip_involutive e he G⟩
          simp only [hS, Set.mem_ofPred_eq]
          exact (ncard_even_edge_graphs_flip_even e he G).mpr hG
  9. The cardinalities satisfy |S| + |S| = 2^{n choose 2}.

    The sets S and Sᶜ partition the set of all simple graphs on Fin n. By `Set.ncard_add_ncard_compl`, |S| + |Sᶜ| is the total number of simple graphs, which equals 2^{n choose 2} by `card_simpleGraph` and `Fintype.card_fin`. Substituting |Sᶜ| = |S| gives |S| + |S| = 2^{n choose 2}.

    lines 100–103

    uses Set.ncard_add_ncard_compl, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin

      have hsum : S.ncard + Sᶜ.ncard = 2 ^ n.choose 2 := by
        rw [Set.ncard_add_ncard_compl, Nat.card_eq_fintype_card, card_simpleGraph,
          Fintype.card_fin]
      rw [← hcongr] at hsum
  10. The number of simple graphs on Fin n with an even number of edges is 2^{n choose 2 - 1}.

    Since n ≥ 2, n choose 2 is strictly positive (`Nat.choose_pos`), so (n choose 2 - 1) + 1 = n choose 2 (`Nat.sub_one_add_one`). Thus 2^{n choose 2} = 2 * 2^{n choose 2 - 1} by `pow_succ'`. Rewriting |S| + |S| as 2 * |S| via `two_mul` yields 2 * |S| = 2 * 2^{n choose 2 - 1}. Cancelling the common factor of 2 via `Nat.mul_left_cancel` concludes that |S| = 2^{n choose 2 - 1}.

    lines 104–111

    uses Nat.choose_pos, Nat.sub_one_add_one, pow_succ', two_mul, Nat.mul_left_cancel

      have hk : 0 < n.choose 2 := Nat.choose_pos hn
      have hk1 : n.choose 2 - 1 + 1 = n.choose 2 := Nat.sub_one_add_one hk.ne'
      have h2 : 2 ^ n.choose 2 = 2 * 2 ^ (n.choose 2 - 1) := by
        conv_lhs => rw [← hk1]
        rw [pow_succ']
      have hh : 2 * S.ncard = 2 * 2 ^ (n.choose 2 - 1) := by
        rw [two_mul]; exact hsum.trans h2
      exact Nat.mul_left_cancel (by norm_num) hh
SimpleGraph.edgeSet_fromEdgeSet
The edge set of a simple graph formed from a set of pairs s is s with all diagonal elements (loops) removed.
Set.mem_sdiff
An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Set.mem_symmDiff
An element belongs to the symmetric difference of s and t if and only if it belongs to s \ t or to t \ s.
Set.mem_singleton_iff
An element belongs to the singleton {b} if and only if it equals b.
Sym2.mem_diagSet
An unordered pair belongs to the diagonal set if and only if its two endpoints are equal (a self-loop).
SimpleGraph.edgeSet_inj.mp
Two simple graphs are equal if and only if their edge sets are equal.
ncard_even_edge_graphs_flip_edgeSet
Toggling a non-loop edge e in graph G replaces its edge set with the symmetric difference of G's edge set and {e}.
symmDiff_symmDiff_cancel_right
The symmetric difference operation satisfies (s Δ t) Δ t = s.
Set.singleton_subset_iff.mpr
A singleton {e} is a subset of s whenever e ∈ s.
Set.symmDiff_def
The symmetric difference of sets s and t is defined as (s \ t) ∪ (t \ s).
Set.sdiff_eq_empty.mpr
If s is a subset of t, then s \ t is empty.
Set.union_empty
The union of any set with the empty set is the set itself.
Set.ncard_sdiff
If s ⊆ t, then the cardinality of t \ s is |t| - |s|.
Set.ncard_singleton
The cardinality of any singleton set is 1.
Set.ncard_pos
A finite set has strictly positive cardinality if and only if it is nonempty.
Nat.even_sub
For natural numbers n ≤ m, the difference m - n is even if and only if m and n have the same parity.
Set.mem_insert_iff
An element belongs to insert a s if and only if it equals a or belongs to s.
Or.inr
Constructs a proof of a ∨ b from a proof of the right disjunct b.
Or.inl
Constructs a proof of a ∨ b from a proof of the left disjunct a.
Set.ncard_insert_of_notMem
Inserting an element not in s into a finite set s increases its cardinality by 1.
Nat.even_add_one
For any natural number n, n + 1 is even if and only if n is not even.
SimpleGraph.edgeFinset_card
The cardinality of the edge finset of G equals the cardinality of the edge set as a finite type.
Set.ncard_eq_toFinset_card'
The cardinality of a set equals the cardinality of its finset representation.
Set.toFinset_card
The cardinality of the finset representation of a set equals the cardinality of the subtype as a finite type.
ncard_even_edge_graphs_even_iff
The parity of the finset edge count of G is equivalent to the parity of its set edge count.
ncard_even_edge_graphs_flip_ncard_even
Toggling a non-loop edge in G inverts the parity of its set edge count.
Sym2.mk_isDiag_iff
An unordered pair s(x, y) is diagonal if and only if x = y.
congrArg
Equality is preserved under applying a function: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.val
The canonical embedding from Fin n to ℕ mapping an index to its underlying natural number.
Set.ncard_congr
If there is a bijection between two finite sets s and t, their cardinalities are equal.
ncard_even_edge_graphs_flip_even
Toggling a non-loop edge in G inverts the parity of its finset edge count.
ncard_even_edge_graphs_flip_involutive
Toggling the same non-loop edge twice is the identity operation on simple graphs.
Set.ncard_add_ncard_compl
The sum of the cardinalities of a set and its complement equals the cardinality of the ambient type.
Nat.card_eq_fintype_card
The cardinality of a finite type equals its Fintype.card.
card_simpleGraph
The number of simple graphs on a finite vertex set V is 2^{|V| choose 2}.
Fintype.card_fin
The cardinality of Fin n is n.
Nat.choose_pos
If k ≤ n, then the binomial coefficient n choose k is strictly positive.
Nat.sub_one_add_one
If a ≠ 0, then (a - 1) + 1 = a.
pow_succ'
In any monoid, a^{n+1} = a * a^n.
two_mul
In any semiring, 2 * n = n + n.
Nat.mul_left_cancel
If n > 0 and n * m = n * k, then m = k.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Toggle the edge `e` in the graph `G`. -/private def ncard_even_edge_graphs_flip {n : ℕ} (e : Sym2 (Fin n)) (G : SimpleGraph (Fin n)) :    SimpleGraph (Fin n) :=  SimpleGraph.fromEdgeSet (symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))))/-- The edge set of the toggled graph is the symmetric difference of edge sets. -/private theorem ncard_even_edge_graphs_flip_edgeSet {n : ℕ} (e : Sym2 (Fin n)) (he : ¬ e.IsDiag)    (G : SimpleGraph (Fin n)) :    (ncard_even_edge_graphs_flip e G).edgeSet = symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))) := by  simp only [ncard_even_edge_graphs_flip, SimpleGraph.edgeSet_fromEdgeSet]  ext x  simp only [Set.mem_sdiff, Set.mem_symmDiff, Set.mem_singleton_iff, Sym2.mem_diagSet]  constructor  · rintro ⟨h, -⟩; exact h  · intro h    refine ⟨h, ?_⟩    rcases h with ⟨hxG, hxe⟩ | ⟨hxe, hxG⟩    · exact G.not_isDiag_of_mem_edgeSet hxG    · subst hxe; exact he/-- Toggling the same non-loop edge twice is the identity. -/private theorem ncard_even_edge_graphs_flip_involutive {n : ℕ} (e : Sym2 (Fin n))    (he : ¬ e.IsDiag) (G : SimpleGraph (Fin n)) :    ncard_even_edge_graphs_flip e (ncard_even_edge_graphs_flip e G) = G := by  apply SimpleGraph.edgeSet_inj.mp  rw [ncard_even_edge_graphs_flip_edgeSet e he (ncard_even_edge_graphs_flip e G),    ncard_even_edge_graphs_flip_edgeSet e he G]  exact symmDiff_symmDiff_cancel_right ({e} : Set (Sym2 (Fin n))) G.edgeSet/-- Toggling a non-loop edge flips the parity of the number of edges. -/private theorem ncard_even_edge_graphs_flip_ncard_even {n : ℕ} (e : Sym2 (Fin n))    (he : ¬ e.IsDiag) (G : SimpleGraph (Fin n)) :    Even (ncard_even_edge_graphs_flip e G).edgeSet.ncard ↔ ¬ Even G.edgeSet.ncard := by  classical  rw [ncard_even_edge_graphs_flip_edgeSet e he G]  by_cases hmem : e ∈ G.edgeSet  · have hsub : ({e} : Set (Sym2 (Fin n))) ⊆ G.edgeSet := Set.singleton_subset_iff.mpr hmem    have hset : symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))) = G.edgeSet \ {e} := by      rw [Set.symmDiff_def, Set.sdiff_eq_empty.mpr hsub, Set.union_empty]    rw [hset, Set.ncard_sdiff hsub, Set.ncard_singleton]    have hpos : 1 ≤ G.edgeSet.ncard := by      have h0 : 0 < G.edgeSet.ncard := by        rw [Set.ncard_pos]        exact ⟨e, hmem⟩      omega    rw [Nat.even_sub hpos]    simp  · have hset : symmDiff G.edgeSet ({e} : Set (Sym2 (Fin n))) = insert e G.edgeSet := by      ext x      simp only [Set.mem_symmDiff, Set.mem_singleton_iff, Set.mem_insert_iff]      constructor      · rintro (⟨hx, -⟩ | ⟨rfl, -⟩)        · exact Or.inr hx        · exact Or.inl rfl      · rintro (rfl | hx)        · exact Or.inr ⟨rfl, hmem⟩        · exact Or.inl ⟨hx, fun hxe => hmem (hxe ▸ hx)⟩    rw [hset, Set.ncard_insert_of_notMem hmem, Nat.even_add_one]/-- The parity of the number of edges equals the parity of the edge-set cardinality. -/private theorem ncard_even_edge_graphs_even_iff {n : ℕ} (G : SimpleGraph (Fin n)) :    (open Classical in Even G.edgeFinset.card ↔ Even G.edgeSet.ncard) := by  classical  rw [SimpleGraph.edgeFinset_card, Set.ncard_eq_toFinset_card', Set.toFinset_card]/-- Toggling a non-loop edge flips the parity of the edge count. -/private theorem ncard_even_edge_graphs_flip_even {n : ℕ} (e : Sym2 (Fin n))    (he : ¬ e.IsDiag) (G : SimpleGraph (Fin n)) :    (open Classical in      Even (ncard_even_edge_graphs_flip e G).edgeFinset.card ↔ ¬ Even G.edgeFinset.card) := by  rw [ncard_even_edge_graphs_even_iff, ncard_even_edge_graphs_even_iff,    ncard_even_edge_graphs_flip_ncard_even e he G]/-- Exactly half of all simple graphs on Fin n have an even number of edges for n ≥ 2. -/theorem ncard_even_edge_graphs (n : ℕ) (hn : 2 ≤ n) :    Set.ncard (open Classical in {G : SimpleGraph (Fin n) | Even G.edgeFinset.card}) = 2 ^ (n.choose 2 - 1) := by  classical  set e : Sym2 (Fin n) := s(⟨0, by omega⟩, ⟨1, by omega⟩)  have he : ¬ e.IsDiag := by    rw [Sym2.mk_isDiag_iff]    intro h    have h2 : (0 : ℕ) = 1 := congrArg Fin.val h    omega  set S : Set (SimpleGraph (Fin n)) := {G | Even G.edgeFinset.card} with hS  have hcongr : S.ncard = Sᶜ.ncard := by    refine Set.ncard_congr (fun G _ => ncard_even_edge_graphs_flip e G) ?_ ?_ ?_    · intro G hG      simp only [hS, Set.mem_ofPred_eq] at hG      simp only [Set.mem_compl_iff, hS, Set.mem_ofPred_eq]      exact fun h => (ncard_even_edge_graphs_flip_even e he G).mp h hG    · intro G₁ G₂ _ _ h      rw [← ncard_even_edge_graphs_flip_involutive e he G₁,        ← ncard_even_edge_graphs_flip_involutive e he G₂, h]    · intro G hG      simp only [Set.mem_compl_iff, hS, Set.mem_ofPred_eq] at hG      refine ⟨ncard_even_edge_graphs_flip e G, ?_,        ncard_even_edge_graphs_flip_involutive e he G⟩      simp only [hS, Set.mem_ofPred_eq]      exact (ncard_even_edge_graphs_flip_even e he G).mpr hG  have hsum : S.ncard + Sᶜ.ncard = 2 ^ n.choose 2 := by    rw [Set.ncard_add_ncard_compl, Nat.card_eq_fintype_card, card_simpleGraph,      Fintype.card_fin]  rw [← hcongr] at hsum  have hk : 0 < n.choose 2 := Nat.choose_pos hn  have hk1 : n.choose 2 - 1 + 1 = n.choose 2 := Nat.sub_one_add_one hk.ne'  have h2 : 2 ^ n.choose 2 = 2 * 2 ^ (n.choose 2 - 1) := by    conv_lhs => rw [← hk1]    rw [pow_succ']  have hh : 2 * S.ncard = 2 * 2 ^ (n.choose 2 - 1) := by    rw [two_mul]; exact hsum.trans h2  exact Nat.mul_left_cancel (by norm_num) hh
See it in the graphDiscuss this resultChallenge it