AFTD Auto-Formalizing Theoretical Domains

k22_code_card_le

theoremverifiedformalization

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

Statement

theorem k22_code_card_le (n : ℕ) (hn : 4 ≤ n)
    (C : Set (SimpleGraph (Fin n))) (hC : is_kst_code 2 2 n C) :
    (n - 2) * Set.ncard C ≤ 2 ^ n.choose 2
Formalizes
arXiv:2301.13305, Proposition 1.5; arXiv:2610.35136, Proposition 3.1
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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
  • k22_code_max_density_leFor every natural number n with 4 ≤ n, the maximum density of a K_{2,2}-code on Fin n, kst_code_max_density 2 2 n, is at most 1 / ((n : ℝ)…

Read back from the Lean

For any natural number $n \ge 4$ and any set $C$ of simple graphs on vertices $\mathrm{Fin}(n)$, if $C$ is a $(2, 2)$-code—meaning that for every pair of distinct graphs $G, G' \in C$ and any two disjoint 2-element subsets $A, B \subseteq \mathrm{Fin}(n)$, the symmetric difference of $G$ and $G'$ is not equal to the complete bipartite graph between $A$ and $B$—then $(n - 2) \cdot |C| \le 2^{\binom{n}{2}}$, where $|C| = \mathrm{Set.ncard}(C)$.

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 bound the cardinality of a K_{2,2}-code C on n vertices (n ≥ 4), we fix two vertices A = {u, v} and consider the remaining n - 2 vertices R. For each y ∈ R, we define a graph H(y) such that for distinct y, z ∈ R, the symmetric difference H(y) ∆ H(z) is the complete bipartite graph between A and {y, z}. We then define an encoding map f(G, y) = G ∆ H(y) from C × R to the set of all simple graphs on n vertices and prove that f is injective, because a collision between distinct y1, y2 would mean G1 ∆ G2 is a complete bipartite graph K_{2,2}, violating the code property. Since the total number of graphs on n vertices is 2^(n.choose 2), injectivity yields (n - 2) * |C| ≤ 2^(n.choose 2).

  1. Introduce the helper lemma statement and show that r, y, and z are outside A = {u, v}

    The vertices u = 0, v = 1, r = 2 in Fin n are well-defined because 4 ≤ n. By definition, A = {u, v} and R is the complement of A. Given y, z ∈ R, neither y nor z belongs to A. Furthermore, r ∉ A because r = 2 cannot equal 0 or 1.

    lines 1–19

    uses Finset.mem_sdiff.mp, Fin.mk.inj

    lemma k22_code_card_le_H_symmDiff {n : ℕ} (hn : 4 ≤ n) :
        let u : Fin n := ⟨0, by omega⟩
        let v : Fin n := ⟨1, by omega⟩
        let r : Fin n := ⟨2, by omega⟩
        let A : Finset (Fin n) := {u, v}
        let R : Finset (Fin n) := Finset.univ \ A
        let H : Fin n → SimpleGraph (Fin n) := fun y =>
          if y = r then ⊥ else SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤
        ∀ ⦃y z : Fin n⦄, y ∈ R → z ∈ R → y ≠ z →
          symmDiff (H y) (H z) = SimpleGraph.between (A : Set (Fin n)) (↑({y, z} : Finset (Fin n))) ⊤ := by
      intro u v r A R H y z hy hz hyz
      have hyA : y ∉ A := (Finset.mem_sdiff.mp hy).2
      have hzA : z ∉ A := (Finset.mem_sdiff.mp hz).2
      have hrA : r ∉ A := by
        intro h
        have : r = u ∨ r = v := by simpa [A] using h
        rcases this with h1 | h2
        · have := Fin.mk.inj h1; contradiction
        · have := Fin.mk.inj h2; contradiction
  2. If y = r, then H(y) ∆ H(z) is the complete bipartite graph between A and {y, z}

    When y = r, we have H(y) = H(r) = ⊥ by definition of H. Since y ≠ z, z ≠ r, so H(z) is the complete bipartite graph between A and {r, z}. The symmetric difference ⊥ ∆ H(z) simplifies directly to H(z), which is the complete bipartite graph between A and {r, z} = {y, z}.

    lines 20–25

    uses if_pos, if_neg, bot_symmDiff

      if hyr : y = r then
        subst hyr
        have hzr : z ≠ r := hyz.symm
        have hHr : H r = ⊥ := if_pos rfl
        have hHz : H z = SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤ := if_neg hzr
        rw [hHr, hHz, bot_symmDiff]
  3. If z = r and y ≠ r, then H(y) ∆ H(z) is the complete bipartite graph between A and {y, z}

    When z = r, H(z) = ⊥, while H(y) is the complete bipartite graph between A and {r, y}. The symmetric difference H(y) ∆ ⊥ simplifies to H(y). Since the unordered pair {r, y} is identical to {y, r} = {y, z}, this equals the bipartite graph between A and {y, z}.

    lines 26–36

    uses if_pos, if_neg, symmDiff_bot, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton

      else
        if hzr : z = r then
          subst hzr
          have hHr : H r = ⊥ := if_pos rfl
          have hHy : H y = SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤ := if_neg hyr
          rw [hHr, hHy, symmDiff_bot]
          congr 1
          ext a
          simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]
          tauto
        else
  4. If y ≠ r and z ≠ r, then H(y) ∆ H(z) is the complete bipartite graph between A and {y, z}

    When neither y nor z equals r, H(y) and H(z) are complete bipartite graphs between A and {r, y} and between A and {r, z}, respectively. We check adjacency of any edge {a, b} in the symmetric difference. Edges within A or outside A cannot exist in either graph. If one endpoint a is in A and the other b is outside A, edges to r appear in both H(y) and H(z) and thus cancel out in the symmetric difference, while an edge to y appears only in H(y) and an edge to z appears only in H(z). Thus the symmetric difference contains exactly the edges between A and {y, z}.

    lines 37–71

    uses if_neg, Ne.symm, SimpleGraph.between_adj, SimpleGraph.top_adj, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, eq_or_ne

          have hHy : H y = SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤ := if_neg hyr
          have hHz : H z = SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤ := if_neg hzr
          have hyr' : r ≠ y := Ne.symm hyr
          have hzr' : r ≠ z := Ne.symm hzr
          rw [hHy, hHz]
          ext a b
          change (SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤).Adj a b ∧ ¬ (SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤).Adj a b ∨
            (SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤).Adj a b ∧ ¬ (SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤).Adj a b ↔
            (SimpleGraph.between (A : Set (Fin n)) (↑({y, z} : Finset (Fin n))) ⊤).Adj a b
          simp only [SimpleGraph.between_adj, SimpleGraph.top_adj, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]
          by_cases ha : a ∈ A <;> by_cases hb : b ∈ A
          · have h1 : a ≠ r := fun h => hrA (h ▸ ha)
            have h2 : a ≠ y := fun h => hyA (h ▸ ha)
            have h3 : a ≠ z := fun h => hzA (h ▸ ha)
            have h4 : b ≠ r := fun h => hrA (h ▸ hb)
            have h5 : b ≠ y := fun h => hyA (h ▸ hb)
            have h6 : b ≠ z := fun h => hzA (h ▸ hb)
            simp [ha, hb, h1, h2, h3, h4, h5, h6]
          · have hab : a ≠ b := fun h => hb (h ▸ ha)
            rcases eq_or_ne b r with rfl | hbr
            · simp [ha, hb, hab, hzr', hyr']
            · rcases eq_or_ne b y with rfl | hby
              · simp [ha, hb, hab, hyz, hbr]
              · rcases eq_or_ne b z with rfl | hbz
                · simp [ha, hb, hab, hyz.symm, hbr]
                · simp [ha, hb, hab, hbr, hby, hbz]
          · have hab : a ≠ b := fun h => ha (h.symm ▸ hb)
            rcases eq_or_ne a r with rfl | har
            · simp [ha, hb, hab, hzr', hyr']
            · rcases eq_or_ne a y with rfl | hay
              · simp [ha, hb, hab, hyz, har]
              · rcases eq_or_ne a z with rfl | haz
                · simp [ha, hb, hab, hyz.symm, har]
                · simp [ha, hb, hab, har, hay, haz]
          · simp [ha, hb]
  5. Construct the vertex sets A of size 2 and R of size n - 2

    Define u = 0, v = 1, r = 2 in Fin n. Because u ≠ v (as 0 ≠ 1), the set A = {u, v} has size 2. Its complement R = univ \ A therefore has cardinality n - 2.

    lines 72–87

    uses Fin.mk.inj, Finset.card_pair, Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Fintype.card_fin

    /-- Every K_{2,2}-code C on Fin n for n ≥ 4 satisfies (n - 2) * Set.ncard C ≤ 2 ^ (n.choose 2). -/
    theorem k22_code_card_le (n : ℕ) (hn : 4 ≤ n)
        (C : Set (SimpleGraph (Fin n))) (hC : is_kst_code 2 2 n C) :
        (n - 2) * Set.ncard C ≤ 2 ^ n.choose 2 := by
      let u : Fin n := ⟨0, by omega⟩
      let v : Fin n := ⟨1, by omega⟩
      let r : Fin n := ⟨2, by omega⟩
      let A : Finset (Fin n) := {u, v}
      let R : Finset (Fin n) := Finset.univ \ A
      have huv : u ≠ v := by intro h; have := Fin.mk.inj h; contradiction
      have hA : A.card = 2 := Finset.card_pair huv
      have hR : R.card = n - 2 := by
        have h := Finset.card_sdiff_of_subset (Finset.subset_univ A)
        rw [Finset.card_univ, Fintype.card_fin, hA] at h
        exact h
  6. Define the graph family H and the encoding map f on C × R

    For each vertex y, H(y) is the empty graph if y = r, and the complete bipartite graph between A and {r, y} otherwise. We define f(G, y) = G ∆ H(y) from C × R to simple graphs on Fin n.

    lines 88–90

      let H : Fin n → SimpleGraph (Fin n) := fun y =>
        if y = r then ⊥ else SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤
      let f : SimpleGraph (Fin n) × Fin n → SimpleGraph (Fin n) := fun p => symmDiff p.1 (H p.2)
  7. If f(G1, y1) = f(G2, y2) with y1 = y2, then G1 = G2

    The equation G1 ∆ H(y1) = G2 ∆ H(y2) rearranges by group properties of symmetric difference to G1 ∆ G2 = H(y1) ∆ H(y2). When y1 = y2, the right side is ⊥, which implies G1 = G2 and thus (G1, y1) = (G2, y2).

    lines 91–111

    uses Set.mem_prod, Finset.mem_coe, symmDiff_assoc, symmDiff_self, bot_symmDiff, symmDiff_comm, symmDiff_eq_bot

      have hinj : Set.InjOn f (C ×ˢ (R : Set (Fin n))) := by
        intro p1 hp1 p2 hp2 hf
        rcases p1 with ⟨G1, y1⟩
        rcases p2 with ⟨G2, y2⟩
        simp only [Set.mem_prod, Finset.mem_coe] at hp1 hp2
        have hG1 : G1 ∈ C := hp1.1
        have hy1 : y1 ∈ R := hp1.2
        have hG2 : G2 ∈ C := hp2.1
        have hy2 : y2 ∈ R := hp2.2
        dsimp [f] at hf
        have H_eq : symmDiff G1 G2 = symmDiff (H y1) (H y2) := by
          have H_cancel (x y z : SimpleGraph (Fin n)) : symmDiff (symmDiff x y) (symmDiff y z) = symmDiff x z := by
            rw [symmDiff_assoc, ← symmDiff_assoc y, symmDiff_self, bot_symmDiff]
          have h1 : symmDiff (symmDiff G1 (H y1)) (symmDiff (H y1) G2) = symmDiff (symmDiff G2 (H y2)) (symmDiff (H y1) G2) := by rw [hf]
          rw [H_cancel G1 (H y1) G2] at h1
          rw [symmDiff_comm G2 (H y2), symmDiff_comm (H y1) G2, H_cancel (H y2) G2 (H y1), symmDiff_comm (H y2) (H y1)] at h1
          exact h1
        by_cases hy : y1 = y2
        · subst hy
          rw [symmDiff_self, symmDiff_eq_bot] at H_eq
          ext <;> simp [H_eq]
  8. The case y1 ≠ y2 is impossible because C is a K_{2,2}-code

    If y1 ≠ y2, the helper lemma shows that H(y1) ∆ H(y2) is the complete bipartite graph between A and B = {y1, y2}. Since y1, y2 ∈ R, B has size 2 and is disjoint from A (which also has size 2). Thus G1 ∆ G2 is a complete bipartite graph K_{2,2} between A and B. If G1 = G2, then G1 ∆ G2 would be empty, contradicting the presence of an edge between u and y1. Thus G1 ≠ G2, which contradicts the hypothesis that C is a K_{2,2}-code.

    lines 112–135

    uses k22_code_card_le_H_symmDiff, Finset.card_pair, Finset.mem_sdiff.mp, Finset.disjoint_left, Finset.mem_insert, Finset.mem_singleton, symmDiff_self, SimpleGraph.between_adj, SimpleGraph.top_adj, Finset.mem_insert_self, Or.inl

        · exfalso
          have H_H := k22_code_card_le_H_symmDiff hn hy1 hy2 hy
          have hB : ({y1, y2} : Finset (Fin n)).card = 2 := Finset.card_pair hy
          have hy1A : y1 ∉ A := (Finset.mem_sdiff.mp hy1).2
          have hy2A : y2 ∉ A := (Finset.mem_sdiff.mp hy2).2
          have hdisj : Disjoint A {y1, y2} := by
            rw [Finset.disjoint_left]
            intro x hx
            simp only [Finset.mem_insert, Finset.mem_singleton]
            rintro (rfl | rfl)
            · exact hy1A hx
            · exact hy2A hx
          have hdiff : symmDiff G1 G2 = SimpleGraph.between (A : Set (Fin n)) (↑({y1, y2} : Finset (Fin n))) ⊤ :=
            H_eq.trans H_H
          have hG12 : G1 ≠ G2 := by
            intro heq
            subst heq
            rw [symmDiff_self] at hdiff
            have h_adj : (SimpleGraph.between (A : Set (Fin n)) (↑({y1, y2} : Finset (Fin n))) ⊤).Adj u y1 := by
              rw [SimpleGraph.between_adj, SimpleGraph.top_adj]
              refine ⟨fun h => hy1A (h ▸ Finset.mem_insert_self u {v}), Or.inl ⟨Finset.mem_insert_self u {v}, Finset.mem_insert_self y1 {y2}⟩⟩
            rw [← hdiff] at h_adj
            exact h_adj
          exact hC hG1 hG2 hG12 A {y1, y2} hdisj hA hB hdiff
  9. Deduce (n - 2) * |C| ≤ 2^(n.choose 2) by cardinality comparison

    Since f is injective on C × R, the image f(C × R) has the same cardinality as C × R, which is |C| * |R| = (n - 2) * |C|. Since every image graph is a simple graph on Fin n, and there are 2^(n.choose 2) such graphs, we obtain (n - 2) * |C| ≤ 2^(n.choose 2). Linear arithmetic completes the goal.

    lines 136–144

    uses Set.subset_univ, Set.ncard_le_ncard, Set.InjOn.ncard_image, Set.ncard_prod, Set.ncard_coe_finset, mul_comm, Set.ncard_univ, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin

      have h1 : Set.ncard (C ×ˢ (R : Set (Fin n))) ≤ Set.ncard (Set.univ : Set (SimpleGraph (Fin n))) := by
        have h_sub : f '' (C ×ˢ (R : Set (Fin n))) ⊆ Set.univ := Set.subset_univ _
        have h_le := Set.ncard_le_ncard h_sub
        rw [Set.InjOn.ncard_image hinj] at h_le
        exact h_le
      rw [Set.ncard_prod, Set.ncard_coe_finset, hR, mul_comm] at h1
      have h2 : Set.ncard (Set.univ : Set (SimpleGraph (Fin n))) = 2 ^ n.choose 2 := by
        rw [Set.ncard_univ, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin]
      omega
Finset.mem_sdiff.mp
If an element is in s \ t, then it is in s and not in t.
Fin.mk.inj
Equality of two elements of Fin n implies equality of their underlying values.
if_pos
If a proposition c holds, then (if c then t else e) = t.
if_neg
If a proposition c does not hold, then (if c then t else e) = e.
bot_symmDiff
The symmetric difference of the bottom element and a is a.
symmDiff_bot
The symmetric difference of a and the bottom element is a.
Finset.mem_coe
Membership in the set coercion of a finset is equivalent to membership in the finset.
Finset.mem_insert
Membership in insert b s is equivalent to being equal to b or belonging to s.
Finset.mem_singleton
Membership in the singleton {a} is equivalent to being equal to a.
Ne.symm
Symmetry of inequality: if a ≠ b then b ≠ a.
SimpleGraph.between_adj
Vertices v and w are adjacent in the bipartite graph SimpleGraph.between s t G iff they are adjacent in G and one vertex is in s while the other is in t.
SimpleGraph.top_adj
In the complete graph ⊤, vertices v and w are adjacent iff v ≠ w.
eq_or_ne
Any two elements x and y are either equal or not equal.
Finset.card_pair
The cardinality of a pair {a, b} with a ≠ b is 2.
Finset.card_sdiff_of_subset
If s ⊆ t, then the cardinality of t \ s is |t| - |s|.
Finset.subset_univ
Every finset s is a subset of the universal finset.
Finset.card_univ
The cardinality of the universal finset of a type is the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
Set.mem_prod
A pair p is in the Cartesian product s ×ˢ t iff p.1 ∈ s and p.2 ∈ t.
symmDiff_assoc
Symmetric difference is associative.
symmDiff_self
The symmetric difference of an element with itself is the bottom element.
symmDiff_comm
Symmetric difference is commutative.
symmDiff_eq_bot
The symmetric difference of a and b is the bottom element iff a = b.
k22_code_card_le_H_symmDiff
For distinct y, z in R, H(y) ∆ H(z) is the complete bipartite graph between A and {y, z}.
Finset.disjoint_left
Two finsets are disjoint iff no element of the first belongs to the second.
Finset.mem_insert_self
The element a belongs to insert a s.
Or.inl
From a, infer a ∨ b.
Set.subset_univ
Every set is a subset of the universal set.
Set.ncard_le_ncard
If s ⊆ t and t is finite, then |s| ≤ |t|.
Set.InjOn.ncard_image
An injective map on s preserves set cardinality.
Set.ncard_prod
The cardinality of s ×ˢ t is |s| * |t|.
Set.ncard_coe_finset
The set cardinality of a coerced finset equals its finset cardinality.
mul_comm
Multiplication of natural numbers is commutative.
Set.ncard_univ
The set cardinality of the universal set of α is the cardinality of α.
Nat.card_eq_fintype_card
For a fintype, its cardinality as a set equals its Fintype cardinality.
card_simpleGraph
The number of simple graphs on a finite vertex set V is 2^(|V|.choose 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

lemma k22_code_card_le_H_symmDiff {n : ℕ} (hn : 4 ≤ n) :    let u : Fin n := ⟨0, by omega⟩    let v : Fin n := ⟨1, by omega⟩    let r : Fin n := ⟨2, by omega⟩    let A : Finset (Fin n) := {u, v}    let R : Finset (Fin n) := Finset.univ \ A    let H : Fin n → SimpleGraph (Fin n) := fun y =>      if y = r then ⊥ else SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤    ∀ ⦃y z : Fin n⦄, y ∈ R → z ∈ R → y ≠ z →      symmDiff (H y) (H z) = SimpleGraph.between (A : Set (Fin n)) (↑({y, z} : Finset (Fin n))) ⊤ := by  intro u v r A R H y z hy hz hyz  have hyA : y ∉ A := (Finset.mem_sdiff.mp hy).2  have hzA : z ∉ A := (Finset.mem_sdiff.mp hz).2  have hrA : r ∉ A := by    intro h    have : r = u ∨ r = v := by simpa [A] using h    rcases this with h1 | h2    · have := Fin.mk.inj h1; contradiction    · have := Fin.mk.inj h2; contradiction  if hyr : y = r then    subst hyr    have hzr : z ≠ r := hyz.symm    have hHr : H r = ⊥ := if_pos rfl    have hHz : H z = SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤ := if_neg hzr    rw [hHr, hHz, bot_symmDiff]  else    if hzr : z = r then      subst hzr      have hHr : H r = ⊥ := if_pos rfl      have hHy : H y = SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤ := if_neg hyr      rw [hHr, hHy, symmDiff_bot]      congr 1      ext a      simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]      tauto    else      have hHy : H y = SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤ := if_neg hyr      have hHz : H z = SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤ := if_neg hzr      have hyr' : r ≠ y := Ne.symm hyr      have hzr' : r ≠ z := Ne.symm hzr      rw [hHy, hHz]      ext a b      change (SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤).Adj a b ∧ ¬ (SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤).Adj a b ∨        (SimpleGraph.between (A : Set (Fin n)) (↑({r, z} : Finset (Fin n))) ⊤).Adj a b ∧ ¬ (SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤).Adj a b ↔        (SimpleGraph.between (A : Set (Fin n)) (↑({y, z} : Finset (Fin n))) ⊤).Adj a b      simp only [SimpleGraph.between_adj, SimpleGraph.top_adj, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton]      by_cases ha : a ∈ A <;> by_cases hb : b ∈ A      · have h1 : a ≠ r := fun h => hrA (h ▸ ha)        have h2 : a ≠ y := fun h => hyA (h ▸ ha)        have h3 : a ≠ z := fun h => hzA (h ▸ ha)        have h4 : b ≠ r := fun h => hrA (h ▸ hb)        have h5 : b ≠ y := fun h => hyA (h ▸ hb)        have h6 : b ≠ z := fun h => hzA (h ▸ hb)        simp [ha, hb, h1, h2, h3, h4, h5, h6]      · have hab : a ≠ b := fun h => hb (h ▸ ha)        rcases eq_or_ne b r with rfl | hbr        · simp [ha, hb, hab, hzr', hyr']        · rcases eq_or_ne b y with rfl | hby          · simp [ha, hb, hab, hyz, hbr]          · rcases eq_or_ne b z with rfl | hbz            · simp [ha, hb, hab, hyz.symm, hbr]            · simp [ha, hb, hab, hbr, hby, hbz]      · have hab : a ≠ b := fun h => ha (h.symm ▸ hb)        rcases eq_or_ne a r with rfl | har        · simp [ha, hb, hab, hzr', hyr']        · rcases eq_or_ne a y with rfl | hay          · simp [ha, hb, hab, hyz, har]          · rcases eq_or_ne a z with rfl | haz            · simp [ha, hb, hab, hyz.symm, har]            · simp [ha, hb, hab, har, hay, haz]      · simp [ha, hb]/-- Every K_{2,2}-code C on Fin n for n ≥ 4 satisfies (n - 2) * Set.ncard C ≤ 2 ^ (n.choose 2). -/theorem k22_code_card_le (n : ℕ) (hn : 4 ≤ n)    (C : Set (SimpleGraph (Fin n))) (hC : is_kst_code 2 2 n C) :    (n - 2) * Set.ncard C ≤ 2 ^ n.choose 2 := by  let u : Fin n := ⟨0, by omega⟩  let v : Fin n := ⟨1, by omega⟩  let r : Fin n := ⟨2, by omega⟩  let A : Finset (Fin n) := {u, v}  let R : Finset (Fin n) := Finset.univ \ A  have huv : u ≠ v := by intro h; have := Fin.mk.inj h; contradiction  have hA : A.card = 2 := Finset.card_pair huv  have hR : R.card = n - 2 := by    have h := Finset.card_sdiff_of_subset (Finset.subset_univ A)    rw [Finset.card_univ, Fintype.card_fin, hA] at h    exact h  let H : Fin n → SimpleGraph (Fin n) := fun y =>    if y = r then ⊥ else SimpleGraph.between (A : Set (Fin n)) (↑({r, y} : Finset (Fin n))) ⊤  let f : SimpleGraph (Fin n) × Fin n → SimpleGraph (Fin n) := fun p => symmDiff p.1 (H p.2)  have hinj : Set.InjOn f (C ×ˢ (R : Set (Fin n))) := by    intro p1 hp1 p2 hp2 hf    rcases p1 with ⟨G1, y1⟩    rcases p2 with ⟨G2, y2⟩    simp only [Set.mem_prod, Finset.mem_coe] at hp1 hp2    have hG1 : G1 ∈ C := hp1.1    have hy1 : y1 ∈ R := hp1.2    have hG2 : G2 ∈ C := hp2.1    have hy2 : y2 ∈ R := hp2.2    dsimp [f] at hf    have H_eq : symmDiff G1 G2 = symmDiff (H y1) (H y2) := by      have H_cancel (x y z : SimpleGraph (Fin n)) : symmDiff (symmDiff x y) (symmDiff y z) = symmDiff x z := by        rw [symmDiff_assoc, ← symmDiff_assoc y, symmDiff_self, bot_symmDiff]      have h1 : symmDiff (symmDiff G1 (H y1)) (symmDiff (H y1) G2) = symmDiff (symmDiff G2 (H y2)) (symmDiff (H y1) G2) := by rw [hf]      rw [H_cancel G1 (H y1) G2] at h1      rw [symmDiff_comm G2 (H y2), symmDiff_comm (H y1) G2, H_cancel (H y2) G2 (H y1), symmDiff_comm (H y2) (H y1)] at h1      exact h1    by_cases hy : y1 = y2    · subst hy      rw [symmDiff_self, symmDiff_eq_bot] at H_eq      ext <;> simp [H_eq]    · exfalso      have H_H := k22_code_card_le_H_symmDiff hn hy1 hy2 hy      have hB : ({y1, y2} : Finset (Fin n)).card = 2 := Finset.card_pair hy      have hy1A : y1 ∉ A := (Finset.mem_sdiff.mp hy1).2      have hy2A : y2 ∉ A := (Finset.mem_sdiff.mp hy2).2      have hdisj : Disjoint A {y1, y2} := by        rw [Finset.disjoint_left]        intro x hx        simp only [Finset.mem_insert, Finset.mem_singleton]        rintro (rfl | rfl)        · exact hy1A hx        · exact hy2A hx      have hdiff : symmDiff G1 G2 = SimpleGraph.between (A : Set (Fin n)) (↑({y1, y2} : Finset (Fin n))) ⊤ :=        H_eq.trans H_H      have hG12 : G1 ≠ G2 := by        intro heq        subst heq        rw [symmDiff_self] at hdiff        have h_adj : (SimpleGraph.between (A : Set (Fin n)) (↑({y1, y2} : Finset (Fin n))) ⊤).Adj u y1 := by          rw [SimpleGraph.between_adj, SimpleGraph.top_adj]          refine ⟨fun h => hy1A (h ▸ Finset.mem_insert_self u {v}), Or.inl ⟨Finset.mem_insert_self u {v}, Finset.mem_insert_self y1 {y2}⟩⟩        rw [← hdiff] at h_adj        exact h_adj      exact hC hG1 hG2 hG12 A {y1, y2} hdisj hA hB hdiff  have h1 : Set.ncard (C ×ˢ (R : Set (Fin n))) ≤ Set.ncard (Set.univ : Set (SimpleGraph (Fin n))) := by    have h_sub : f '' (C ×ˢ (R : Set (Fin n))) ⊆ Set.univ := Set.subset_univ _    have h_le := Set.ncard_le_ncard h_sub    rw [Set.InjOn.ncard_image hinj] at h_le    exact h_le  rw [Set.ncard_prod, Set.ncard_coe_finset, hR, mul_comm] at h1  have h2 : Set.ncard (Set.univ : Set (SimpleGraph (Fin n))) = 2 ^ n.choose 2 := by    rw [Set.ncard_univ, Nat.card_eq_fintype_card, card_simpleGraph, Fintype.card_fin]  omega
See it in the graphDiscuss this resultChallenge it