AFTD Auto-Formalizing Theoretical Domains

is_kst_code_even_edge_graphs

theoremverified

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}.

  1. 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).

    lines 3–12

    uses disjoint_sdiff_sdiff, Finset.card_union_of_disjoint, Finset.card_sdiff_add_card_inter, Finset.inter_comm, Nat.even_iff

      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 ⊢
      omega
  2. 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₂).

    lines 16–22

    uses SimpleGraph.mem_edgeFinset, Finset.mem_symmDiff, SimpleGraph.edgeSet_sup, SimpleGraph.edgeSet_sdiff

      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]
      rfl
  3. 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.

    lines 27–37

    uses Finset.mem_product, Sym2.eq_iff, Finset.mem_inter.mpr, Finset.disjoint_iff_inter_eq_empty.mp, False.elim, Finset.notMem_empty

      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₁)
  4. 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|.

    lines 38–66

    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_product

      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]
  5. 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.

    lines 71–77

    uses is_kst_code_even_edge_graphs_edgeFinset_symmDiff, is_kst_code_even_edge_graphs_even_card_symmDiff

      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'
  6. 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.

    lines 78–84

    uses Finset.ext, SimpleGraph.mem_edgeFinset

      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]
  7. 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.

    lines 85–87

    uses is_kst_code_even_edge_graphs_card_edgeFinset_between_top, Odd.mul, Nat.not_odd_iff_even.mpr

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it