k22_code_card_le
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).
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.
uses
Finset.mem_sdiff.mp,Fin.mk.injlemma 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 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}.
uses
if_pos,if_neg,bot_symmDiffif 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]
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}.
uses
if_pos,if_neg,symmDiff_bot,Finset.mem_coe,Finset.mem_insert,Finset.mem_singletonelse 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
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}.
uses
if_neg,Ne.symm,SimpleGraph.between_adj,SimpleGraph.top_adj,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,eq_or_nehave 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]
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.
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
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.
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)
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).
uses
Set.mem_prod,Finset.mem_coe,symmDiff_assoc,symmDiff_self,bot_symmDiff,symmDiff_comm,symmDiff_eq_bothave 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]
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.
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
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.
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_finhave 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
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 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