ncard_even_edge_graphs
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}.
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}.
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
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).
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
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.
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
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.
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]
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.
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]
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`.
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]
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.
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
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.
uses
Set.ncard_congr,ncard_even_edge_graphs_flip_even,ncard_even_edge_graphs_flip_involutiveset 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
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}.
uses
Set.ncard_add_ncard_compl,Nat.card_eq_fintype_card,card_simpleGraph,Fintype.card_finhave 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
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}.
uses
Nat.choose_pos,Nat.sub_one_add_one,pow_succ',two_mul,Nat.mul_left_cancelhave 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.
- The proof toggles an edge via symmetric difference using `SimpleGraph.fromEdgeSet`. Because `SimpleGraph` forbids self-loops, Lean requires a formal check (in `ncard_even_edge_graphs_flip_edgeSet`) that no diagonal elements are introduced.
- Lean maintains separate notions of cardinality for sets (`Set.ncard`) and finite sets (`Finset.card`), bridged here by `ncard_even_edge_graphs_even_iff`.
- Linear arithmetic over ℕ is discharged automatically by `omega` (for example, showing that the vertices 0 and 1 in `Fin n` are distinct when n ≥ 2).
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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