is_kst_code_even_edge_graphs
Let s and t be odd natural numbers, and let n be a natural number. The set of simple graphs on vertex set [n] with an even number of edges is a K_{s,t}-code.
Statement
theorem is_kst_code_even_edge_graphs (s t n : ℕ) (hs : Odd s) (ht : Odd t) : is_kst_code s t n (open Classical in {G : SimpleGraph (Fin n) | Even G.edgeFinset.card})
- 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
- is_kst_codeA family C of simple graphs on vertex set [n] is a K_{s,t}-code if for every two distinct graphs G, G' in C and every pair of disjoint…
- 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 numbers $s$, $t$, and $n$, if $s$ is odd and $t$ is odd, then the family of simple graphs on vertex set $\mathrm{Fin}\;n$ with an even number of edges forms a $K_{s,t}$-code in the sense of is_kst_code s t n.
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 show that the family of graphs with an even number of edges forms a K_{s,t}-code for odd s and t, we argue by contradiction. Suppose two distinct graphs G and G' with an even number of edges have symmetric difference equal to a complete bipartite graph K_{A,B} between disjoint sets of vertices with sizes s and t. On one hand, the edge set of G ∆ G' is the symmetric difference of their edge sets, which must have an even number of edges because the symmetric difference of two sets of even cardinality is even. On the other hand, the complete bipartite graph K_{A,B} has exactly |A| * |B| = s * t edges, which is odd because both s and t are odd. This parity contradiction shows that no two such graphs can have symmetric difference K_{s,t}.
The symmetric difference of two finite sets with even cardinalities has an even cardinality.
The symmetric difference s ∆ t decomposes into the disjoint union of s \ t and t \ s, so |s ∆ t| = |s \ t| + |t \ s|. Since |s| = |s \ t| + |s ∩ t| and |t| = |t \ s| + |s ∩ t|, we obtain |s ∆ t| = |s| + |t| - 2|s ∩ t|. Converting the evenness hypotheses to modulo 2 arithmetic via Nat.even_iff, linear arithmetic (omega) verifies that |s ∆ t| ≡ |s| + |t| - 2|s ∩ t| ≡ 0 (mod 2).
uses
disjoint_sdiff_sdiff,Finset.card_union_of_disjoint,Finset.card_sdiff_add_card_inter,Finset.inter_comm,Nat.even_iffhave hd : Disjoint (s \ t) (t \ s) := disjoint_sdiff_sdiff have h1 : (symmDiff s t).card = (s \ t).card + (t \ s).card := by change (s \ t ∪ t \ s).card = (s \ t).card + (t \ s).card exact Finset.card_union_of_disjoint hd have h2 : s.card = (s \ t).card + (s ∩ t).card := (Finset.card_sdiff_add_card_inter s t).symm have h3 : t.card = (t \ s).card + (s ∩ t).card := by rw [Finset.inter_comm] exact (Finset.card_sdiff_add_card_inter t s).symm rw [Nat.even_iff] at hs ht ⊢ omega
The edge finset of the symmetric difference of two simple graphs equals the symmetric difference of their edge finsets.
By extensionality on edges, an edge e belongs to (G₁ ∆ G₂).edgeFinset if and only if it belongs to the edge set of (G₁ \ G₂) ⊔ (G₂ \ G₁). Distributing the edge-set operator over graph join and difference yields (E(G₁) \ E(G₂)) ∪ (E(G₂) \ E(G₁)), which is the definition of the symmetric difference of E(G₁) and E(G₂).
uses
SimpleGraph.mem_edgeFinset,Finset.mem_symmDiff,SimpleGraph.edgeSet_sup,SimpleGraph.edgeSet_sdiffclassical ext e rw [SimpleGraph.mem_edgeFinset, Finset.mem_symmDiff, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeFinset] change e ∈ (G₁ \ G₂ ⊔ G₂ \ G₁).edgeSet ↔ _ rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_sdiff, SimpleGraph.edgeSet_sdiff] rfl
The canonical edge map sending an ordered pair (u, v) to the unordered pair s(u, v) is injective on s × t when s and t are disjoint.
Assume s(u₁, v₁) = s(u₂, v₂) for pairs in s × t. By unordered pair equality (Sym2.eq_iff), either (u₁ = u₂ ∧ v₁ = v₂), which yields equality of the pairs, or (u₁ = v₂ ∧ v₁ = u₂). In the second case, u₁ ∈ s and u₁ = v₂ ∈ t, so u₁ ∈ s ∩ t. But s and t are disjoint, so s ∩ t = ∅, a contradiction.
uses
Finset.mem_product,Sym2.eq_iff,Finset.mem_inter.mpr,Finset.disjoint_iff_inter_eq_empty.mp,False.elim,Finset.notMem_emptyclassical let f : V × V → Sym2 V := fun (u, v) => s(u, v) have hinj : ∀ x ∈ s ×ˢ t, ∀ y ∈ s ×ˢ t, f x = f y → x = y := by rintro ⟨u₁, v₁⟩ h₁ ⟨u₂, v₂⟩ h₂ heq rw [Finset.mem_product] at h₁ h₂ simp only [f, Sym2.eq_iff] at heq rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · rfl · have hu₁ : u₁ ∈ s ∩ t := Finset.mem_inter.mpr ⟨h₁.1, h₂.2⟩ rw [Finset.disjoint_iff_inter_eq_empty.mp h] at hu₁ exact False.elim (Finset.notMem_empty _ hu₁)
For disjoint sets s and t, the complete bipartite graph between s and t has exactly |s| * |t| edges.
An unordered pair e is an edge of the complete bipartite graph between s and t if and only if its endpoints are distinct and one belongs to s while the other belongs to t. This precisely characterizes the edges as the image of s × t under the pair-forming map f. Because f was shown to be injective on s × t, the number of edges equals the cardinality of s × t, which is |s| * |t|.
uses
SimpleGraph.mem_edgeFinset,Finset.mem_image,Sym2.ind,SimpleGraph.mem_edgeSet,SimpleGraph.between_adj,SimpleGraph.top_adj,Finset.mem_product,Sym2.eq_swap,Sym2.eq_iff,Or.inl,Finset.mem_inter.mpr,Finset.disjoint_iff_inter_eq_empty.mp,Finset.notMem_empty,Or.inr,Finset.card_image_of_injOn,Finset.card_producthave himg : ((⊤ : SimpleGraph V).between (s : Set V) (t : Set V)).edgeFinset = (s ×ˢ t).image f := by ext e rw [SimpleGraph.mem_edgeFinset, Finset.mem_image] induction' e using Sym2.ind with u v simp only [SimpleGraph.mem_edgeSet, SimpleGraph.between_adj, SimpleGraph.top_adj] constructor · rintro ⟨hne, (⟨hu, hv⟩ | ⟨hu, hv⟩)⟩ · refine ⟨(u, v), ?_, rfl⟩ rw [Finset.mem_product] exact ⟨hu, hv⟩ · refine ⟨(v, u), ?_, Sym2.eq_swap⟩ rw [Finset.mem_product] exact ⟨hv, hu⟩ · rintro ⟨⟨a, b⟩, hab, heq⟩ rw [Finset.mem_product] at hab simp only [f, Sym2.eq_iff] at heq rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · refine ⟨?_, Or.inl ⟨hab.1, hab.2⟩⟩ rintro rfl have hab_inter : a ∈ s ∩ t := Finset.mem_inter.mpr ⟨hab.1, hab.2⟩ rw [Finset.disjoint_iff_inter_eq_empty.mp h] at hab_inter exact Finset.notMem_empty _ hab_inter · refine ⟨?_, Or.inr ⟨hab.2, hab.1⟩⟩ rintro rfl have hab_inter : b ∈ s ∩ t := Finset.mem_inter.mpr ⟨hab.1, hab.2⟩ rw [Finset.disjoint_iff_inter_eq_empty.mp h] at hab_inter exact Finset.notMem_empty _ hab_inter rw [himg, Finset.card_image_of_injOn hinj, Finset.card_product]
If two graphs G and G' each have an even number of edges, their symmetric difference graph G ∆ G' also has an even number of edges.
We assume for contradiction that two distinct graphs G and G' with an even number of edges have symmetric difference equal to a complete bipartite graph between disjoint sets of sizes s and t. By Lemma 2, the edge finset of G ∆ G' is the symmetric difference of the edge finsets of G and G'. By Lemma 1, the symmetric difference of two finite sets with even cardinalities has even cardinality, so G ∆ G' has an even number of edges.
uses
is_kst_code_even_edge_graphs_edgeFinset_symmDiff,is_kst_code_even_edge_graphs_even_card_symmDiffclassical intro G G' hG hG' _hdiff A B hAB hA hB heq change Even G.edgeFinset.card at hG change Even G'.edgeFinset.card at hG' have heven : Even (symmDiff G G').edgeFinset.card := by rw [is_kst_code_even_edge_graphs_edgeFinset_symmDiff] exact is_kst_code_even_edge_graphs_even_card_symmDiff G.edgeFinset G'.edgeFinset hG hG'
The complete bipartite graph between A and B must have an even number of edges.
By the assumption that G ∆ G' is equal to the complete bipartite graph between A and B, their edge finsets are identical. Rewriting along this equality, the complete bipartite graph between A and B must have an even number of edges.
uses
Finset.ext,SimpleGraph.mem_edgeFinsethave heq_finset : (symmDiff G G').edgeFinset = ((⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))).edgeFinset := by apply Finset.ext intro e simp [SimpleGraph.mem_edgeFinset, heq] have heven' : Even ((⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))).edgeFinset.card := by rwa [← heq_finset]
Contradiction: the edge count s * t cannot be both even and odd.
By Lemma 3, the complete bipartite graph between disjoint sets A and B has |A| * |B| = s * t edges, so s * t must be even. However, since s and t are both odd, their product s * t is odd (Odd.mul). Since an even number cannot be odd (Nat.not_odd_iff_even.mpr), this produces a contradiction, concluding that the family of even-edge graphs is a K_{s,t}-code.
uses
is_kst_code_even_edge_graphs_card_edgeFinset_between_top,Odd.mul,Nat.not_odd_iff_even.mprrw [is_kst_code_even_edge_graphs_card_edgeFinset_between_top A B hAB, hA, hB] at heven' have hodd : Odd (s * t) := Odd.mul hs ht exact (Nat.not_odd_iff_even.mpr heven') hodd
disjoint_sdiff_sdiff- For any elements x and y in a generalized Boolean algebra, the differences x \ y and y \ x are disjoint.
Finset.card_union_of_disjoint- If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
Finset.card_sdiff_add_card_inter- For finite sets s and t, the size of their difference plus the size of their intersection equals the size of s.
Finset.inter_comm- Intersection of finite sets is commutative.
Nat.even_iff- A natural number is even if and only if its remainder modulo 2 is zero.
SimpleGraph.mem_edgeFinset- An edge belongs to the finite edge set of a simple graph if and only if it belongs to its underlying edge set.
Finset.mem_symmDiff- An element belongs to the symmetric difference of two sets if and only if it belongs to exactly one of them.
SimpleGraph.edgeSet_sup- The edge set of the union of two simple graphs is the union of their edge sets.
SimpleGraph.edgeSet_sdiff- The edge set of the difference of two simple graphs is the difference of their edge sets.
Finset.mem_product- An ordered pair belongs to the Cartesian product of two finite sets if and only if its first component is in the first set and its second component is in the second set.
Sym2.eq_iff- Two unordered pairs are equal if and only if their elements are pairwise equal in the same or opposite order.
Finset.mem_inter.mpr- If an element belongs to both sets s and t, it belongs to their intersection.
Finset.disjoint_iff_inter_eq_empty.mp- Two finite sets are disjoint if and only if their intersection is empty (forward direction).
False.elim- From a contradiction (falsehood), any proposition follows.
Finset.notMem_empty- The empty set contains no elements.
Finset.mem_image- An element belongs to the image of a finite set under f if and only if it is the image of some element in that set.
Sym2.ind- A property holds for all unordered pairs if it holds for all canonical representations s(x, y).
SimpleGraph.mem_edgeSet- An unordered pair of vertices forms an edge in a simple graph if and only if the vertices are adjacent.
SimpleGraph.between_adj- Two vertices are adjacent in the subgraph between s and t if and only if they are adjacent in G and one vertex is in s while the other is in t.
SimpleGraph.top_adj- Two vertices are adjacent in the complete graph ⊤ if and only if they are distinct.
Sym2.eq_swap- An unordered pair is symmetric with respect to swapping its endpoints: s(a, b) = s(b, a).
Or.inl- If a proposition holds, then any disjunction with it on the left holds.
Or.inr- If a proposition holds, then any disjunction with it on the right holds.
Finset.card_image_of_injOn- If a function is injective on a finite set, the cardinality of its image equals the cardinality of the set.
Finset.card_product- The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
is_kst_code_even_edge_graphs_edgeFinset_symmDiff- The edge finset of the symmetric difference of two simple graphs equals the symmetric difference of their edge finsets.
is_kst_code_even_edge_graphs_even_card_symmDiff- The symmetric difference of two finite sets with even cardinalities has even cardinality.
Finset.ext- Two finite sets are equal if they contain the same elements.
is_kst_code_even_edge_graphs_card_edgeFinset_between_top- For disjoint vertex sets s and t, the complete bipartite graph between s and t has |s| * |t| edges.
Odd.mul- The product of two odd numbers is odd.
Nat.not_odd_iff_even.mpr- If a natural number is even, then it is not odd.
- The Lean formalization represents undirected edges as elements of the quotient type `Sym2 V` (unordered pairs), requiring case analyses on the orientation of pairs $(u, v)$ versus $(v, u)$.
- The parity calculation for the symmetric difference of two sets of even size is completed using the `omega` decision procedure for Presburger arithmetic.
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.
lemma is_kst_code_even_edge_graphs_even_card_symmDiff {α : Type*} [DecidableEq α] (s t : Finset α) (hs : Even s.card) (ht : Even t.card) : Even (symmDiff s t).card := by have hd : Disjoint (s \ t) (t \ s) := disjoint_sdiff_sdiff have h1 : (symmDiff s t).card = (s \ t).card + (t \ s).card := by change (s \ t ∪ t \ s).card = (s \ t).card + (t \ s).card exact Finset.card_union_of_disjoint hd have h2 : s.card = (s \ t).card + (s ∩ t).card := (Finset.card_sdiff_add_card_inter s t).symm have h3 : t.card = (t \ s).card + (s ∩ t).card := by rw [Finset.inter_comm] exact (Finset.card_sdiff_add_card_inter t s).symm rw [Nat.even_iff] at hs ht ⊢ omegalemma is_kst_code_even_edge_graphs_edgeFinset_symmDiff {V : Type*} [Fintype V] [DecidableEq V] (G₁ G₂ : SimpleGraph V) : open Classical in (symmDiff G₁ G₂).edgeFinset = symmDiff G₁.edgeFinset G₂.edgeFinset := by classical ext e rw [SimpleGraph.mem_edgeFinset, Finset.mem_symmDiff, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeFinset] change e ∈ (G₁ \ G₂ ⊔ G₂ \ G₁).edgeSet ↔ _ rw [SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_sdiff, SimpleGraph.edgeSet_sdiff] rfllemma is_kst_code_even_edge_graphs_card_edgeFinset_between_top {V : Type*} [Fintype V] [DecidableEq V] (s t : Finset V) (h : Disjoint s t) : open Classical in ((⊤ : SimpleGraph V).between (s : Set V) (t : Set V)).edgeFinset.card = s.card * t.card := by classical let f : V × V → Sym2 V := fun (u, v) => s(u, v) have hinj : ∀ x ∈ s ×ˢ t, ∀ y ∈ s ×ˢ t, f x = f y → x = y := by rintro ⟨u₁, v₁⟩ h₁ ⟨u₂, v₂⟩ h₂ heq rw [Finset.mem_product] at h₁ h₂ simp only [f, Sym2.eq_iff] at heq rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · rfl · have hu₁ : u₁ ∈ s ∩ t := Finset.mem_inter.mpr ⟨h₁.1, h₂.2⟩ rw [Finset.disjoint_iff_inter_eq_empty.mp h] at hu₁ exact False.elim (Finset.notMem_empty _ hu₁) have himg : ((⊤ : SimpleGraph V).between (s : Set V) (t : Set V)).edgeFinset = (s ×ˢ t).image f := by ext e rw [SimpleGraph.mem_edgeFinset, Finset.mem_image] induction' e using Sym2.ind with u v simp only [SimpleGraph.mem_edgeSet, SimpleGraph.between_adj, SimpleGraph.top_adj] constructor · rintro ⟨hne, (⟨hu, hv⟩ | ⟨hu, hv⟩)⟩ · refine ⟨(u, v), ?_, rfl⟩ rw [Finset.mem_product] exact ⟨hu, hv⟩ · refine ⟨(v, u), ?_, Sym2.eq_swap⟩ rw [Finset.mem_product] exact ⟨hv, hu⟩ · rintro ⟨⟨a, b⟩, hab, heq⟩ rw [Finset.mem_product] at hab simp only [f, Sym2.eq_iff] at heq rcases heq with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · refine ⟨?_, Or.inl ⟨hab.1, hab.2⟩⟩ rintro rfl have hab_inter : a ∈ s ∩ t := Finset.mem_inter.mpr ⟨hab.1, hab.2⟩ rw [Finset.disjoint_iff_inter_eq_empty.mp h] at hab_inter exact Finset.notMem_empty _ hab_inter · refine ⟨?_, Or.inr ⟨hab.2, hab.1⟩⟩ rintro rfl have hab_inter : b ∈ s ∩ t := Finset.mem_inter.mpr ⟨hab.1, hab.2⟩ rw [Finset.disjoint_iff_inter_eq_empty.mp h] at hab_inter exact Finset.notMem_empty _ hab_inter rw [himg, Finset.card_image_of_injOn hinj, Finset.card_product]/-- The family of graphs with an even number of edges is a K_{s,t}-code when s and t are odd. -/theorem is_kst_code_even_edge_graphs (s t n : ℕ) (hs : Odd s) (ht : Odd t) : is_kst_code s t n (open Classical in {G : SimpleGraph (Fin n) | Even G.edgeFinset.card}) := by classical intro G G' hG hG' _hdiff A B hAB hA hB heq change Even G.edgeFinset.card at hG change Even G'.edgeFinset.card at hG' have heven : Even (symmDiff G G').edgeFinset.card := by rw [is_kst_code_even_edge_graphs_edgeFinset_symmDiff] exact is_kst_code_even_edge_graphs_even_card_symmDiff G.edgeFinset G'.edgeFinset hG hG' have heq_finset : (symmDiff G G').edgeFinset = ((⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))).edgeFinset := by apply Finset.ext intro e simp [SimpleGraph.mem_edgeFinset, heq] have heven' : Even ((⊤ : SimpleGraph (Fin n)).between (A : Set (Fin n)) (B : Set (Fin n))).edgeFinset.card := by rwa [← heq_finset] rw [is_kst_code_even_edge_graphs_card_edgeFinset_between_top A B hAB, hA, hB] at heven' have hodd : Odd (s * t) := Odd.mul hs ht exact (Nat.not_odd_iff_even.mpr heven') hodd