cycle_strong_product_not_has_equivalence_cover_three
For every m ≥ 6 and n ≥ 5, the strong product of cycles C_m and C_n (simple_graph_strong_prod of simple_graph_cycle_power m 1 and simple_graph_cycle_power n 1) cannot be covered by 3 equivalence subgraphs.
Statement
theorem cycle_strong_product_not_has_equivalence_cover_three
(m n : ℕ) (hm : 6 ≤ m) (hn : 5 ≤ n) :
¬ simple_graph_has_equivalence_cover
(simple_graph_strong_prod (simple_graph_cycle_power m 1) (simple_graph_cycle_power n 1)) 3- Related work
- OP-597
- Verified
- 28 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- simple_graph_strong_prodThe strong product of two simple graphs G and H: vertices are pairs (u, v) in V(G) × V(H), and two distinct pairs (u, v) and (u', v') are…
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- simple_graph_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- zmod_intCast_eq_intCast_iff_of_abs_sub_ltTwo integers a, b with |a − b| < n are equal modulo n only if they are equal.
- simple_graph_cycle_power_adj_iff_of_bandwidth_ltWhen k<n, two vertices of the k-th cycle power are adjacent exactly when their difference has a nonzero signed integer representative of…
Read back from the Lean
For all natural numbers $m$ and $n$ such that $6 \le m$ and $5 \le n$, the strong product of the cycle graph on $\mathbb{Z}/m\mathbb{Z}$ (the 1st power of the $m$-cycle) and the cycle graph on $\mathbb{Z}/n\mathbb{Z}$ (the 1st power of the $n$-cycle) does not have an equivalence cover of size 3. That is, there does not exist a family of 3 functions $c : \mathrm{Fin}\ 3 \to (\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z}) \to (\mathbb{Z}/m\mathbb{Z} \times \mathbb{Z}/n\mathbb{Z})$ such that: 1. For every index $s \in \mathrm{Fin}\ 3$ and all vertices $u, v$, if $u \ne v$ and $c(s)(u) = c(s)(v)$, then $u$ and $v$ are adjacent in the strong product graph; and 2. For all vertices $u, v$, if $u$ and $v$ are adjacent in the strong product graph, then there exists some $s \in \mathrm{Fin}\ 3$ such that $c(s)(u) = c(s)(v)$.
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
The proof proceeds by contradiction. Assuming the strong product C_m ⊠ C_n has an equivalence cover of size 3, consider the vertex v₀ = (0, 0) and four of its neighbours v₁ = (1, 1), v₂ = (1, -1), v₃ = (-1, 1), and v₄ = (-1, -1). Each of the four edges {v₀, v_i} must be covered by some equivalence relation s_i ∈ Fin 3. However, because m ≥ 6 and n ≥ 5, the four vertices {v₁, v₂, v₃, v₄} form an independent set in the strong product; if two edges shared the same equivalence relation s_i = s_j, transitivity would force an edge between v_i and v_j. Hence the four indices s₁, s₂, s₃, s₄ ∈ Fin 3 must be pairwise distinct, which contradicts the pigeonhole principle.
In a cycle graph C_k of length k ≥ 5, the vertex 0 is adjacent to both 1 and -1.
Since the bandwidth 1 is strictly less than k, adjacency in C_k between u and v is equivalent to v = u + e for some non-zero integer e with |e| ≤ 1. Setting e = 1 shows that 0 is adjacent to 1, and setting e = -1 shows that 0 is adjacent to -1.
uses
simple_graph_cycle_power_adj_iff_of_bandwidth_lthave : NeZero k := ⟨by omega⟩ have hadj01 : (simple_graph_cycle_power k 1).Adj 0 1 := by rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt k 1 (by omega)] exact ⟨1, by decide, by decide, by ring⟩ have hadj0neg1 : (simple_graph_cycle_power k 1).Adj 0 (-1) := by rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt k 1 (by omega)] exact ⟨-1, by decide, by decide, by ring⟩
In ℤ/kℤ with k ≥ 5, the elements 1 and -1 are distinct.
Assuming 1 = -1 in ℤ/kℤ implies that 2 = 0 in ℤ/kℤ. Because |2 - 0| = 2 < 5 ≤ k, the canonical projection from ℤ to ℤ/kℤ is injective on this interval, which forces 2 = 0 in ℤ, a contradiction.
uses
sub_zero,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lthave hne : (1 : ZMod k) ≠ -1 := by intro h have h2 : ((2 : ℤ) : ZMod k) = ((0 : ℤ) : ZMod k) := by push_cast; linear_combination h have h_bound : |(2 : ℤ) - 0| < (k : ℤ) := by rw [sub_zero, abs_lt]; omega have h_eq : (2 : ℤ) = 0 := by rwa [zmod_intCast_eq_intCast_iff_of_abs_sub_lt k 2 0 h_bound] at h2 omega
In C_k with k ≥ 5, vertices 1 and -1 are not adjacent, completing the cycle properties helper lemma.
If 1 and -1 were adjacent in C_k, their difference would be represented by a non-zero integer e with |e| ≤ 1 satisfying -1 = 1 + e in ℤ/kℤ, so e + 2 = 0 in ℤ/kℤ. Since |(e + 2) - 0| ≤ 3 < k, this forces e + 2 = 0 in ℤ, which contradicts |e| ≤ 1. Combining this with the previous claims finishes the lemma.
uses
simple_graph_cycle_power_adj_iff_of_bandwidth_lt,abs_le,sub_zero,abs_lt,zmod_intCast_eq_intCast_iff_of_abs_sub_lthave hnot : ¬ (simple_graph_cycle_power k 1).Adj (1 : ZMod k) (-1) := by rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt k 1 (by omega)] rintro ⟨e, -, he1, he⟩ have h2 : ((e + 2 : ℤ) : ZMod k) = ((0 : ℤ) : ZMod k) := by push_cast; linear_combination -he rw [abs_le] at he1 have h_bound : |(e + 2) - 0| < (k : ℤ) := by rw [sub_zero, abs_lt]; omega have h_eq : (e + 2 : ℤ) = 0 := by rwa [zmod_intCast_eq_intCast_iff_of_abs_sub_lt k (e + 2) 0 h_bound] at h2 omega exact ⟨hadj01, hadj0neg1, hne, hnot⟩
Assume for contradiction that the strong product G = C_m ⊠ C_n has an equivalence cover of size 3, and obtain the cycle properties for C_m and C_n.
Since m ≥ 6 ≥ 5 and n ≥ 5, we apply the helper lemma to both C_m and C_n. We then assume for contradiction that there exists a 3-equivalence cover c, meaning each c(s, ·) for s ∈ Fin 3 partitions the vertices into cliques in G, and every edge of G is monochromatic under some c(s, ·).
uses
cycle_strong_product_not_has_equivalence_cover_three_cycle_propshave hm5 : 5 ≤ m := by omega rcases cycle_strong_product_not_has_equivalence_cover_three_cycle_props m hm5 with ⟨hadj01_m, hadj0neg1_m, hne_m, hnot_m⟩ rcases cycle_strong_product_not_has_equivalence_cover_three_cycle_props n hn with ⟨hadj01_n, hadj0neg1_n, hne_n, hnot_n⟩ set Gm := simple_graph_cycle_power m 1 set Gn := simple_graph_cycle_power n 1 set G := simple_graph_strong_prod Gm Gn rintro ⟨c, hc_clique, hc_cov⟩
The vertex v₀ = (0, 0) is adjacent in G to each of v₁ = (1, 1), v₂ = (1, -1), v₃ = (-1, 1), and v₄ = (-1, -1).
In the strong product of two graphs, two distinct vertices are adjacent if in each factor their coordinates are either equal or adjacent. Because 0 is adjacent to both 1 and -1 in C_m and in C_n, (0, 0) is adjacent to all four diagonal combinations (±1, ±1).
uses
congr_arg,Prod.fst,Or.inrlet v0 : ZMod m × ZMod n := (0, 0) let v1 : ZMod m × ZMod n := (1, 1) let v2 : ZMod m × ZMod n := (1, -1) let v3 : ZMod m × ZMod n := (-1, 1) let v4 : ZMod m × ZMod n := (-1, -1) have hadj_v0_v1 : G.Adj v0 v1 := ⟨fun h => hadj01_m.ne (congr_arg Prod.fst h), Or.inr hadj01_m, Or.inr hadj01_n⟩ have hadj_v0_v2 : G.Adj v0 v2 := ⟨fun h => hadj01_m.ne (congr_arg Prod.fst h), Or.inr hadj01_m, Or.inr hadj0neg1_n⟩ have hadj_v0_v3 : G.Adj v0 v3 := ⟨fun h => hadj0neg1_m.ne (congr_arg Prod.fst h), Or.inr hadj0neg1_m, Or.inr hadj01_n⟩ have hadj_v0_v4 : G.Adj v0 v4 := ⟨fun h => hadj0neg1_m.ne (congr_arg Prod.fst h), Or.inr hadj0neg1_m, Or.inr hadj0neg1_n⟩
Each of the four edges incident to v₀ is covered by some equivalence subgraph index s_i ∈ Fin 3.
By definition of an equivalence cover, each of the four edges {v₀, v₁}, {v₀, v₂}, {v₀, v₃}, {v₀, v₄} must be covered by at least one equivalence relation, providing indices s₁, s₂, s₃, s₄ ∈ Fin 3 such that c(s_i, v₀) = c(s_i, v_i) for each i ∈ {1, 2, 3, 4}.
rcases hc_cov v0 v1 hadj_v0_v1 with ⟨s1, hs1⟩ rcases hc_cov v0 v2 hadj_v0_v2 with ⟨s2, hs2⟩ rcases hc_cov v0 v3 hadj_v0_v3 with ⟨s3, hs3⟩ rcases hc_cov v0 v4 hadj_v0_v4 with ⟨s4, hs4⟩
The four vertices {v₁, v₂, v₃, v₄} form an independent set in G.
Two vertices in G are adjacent only if both coordinate pairs are equal or adjacent in their respective factor cycles. For any two vertices in {v₁, v₂, v₃, v₄}, at least one coordinate has entries 1 and -1. Since 1 ≠ -1 and 1 is not adjacent to -1 in both C_m (with m ≥ 6) and C_n (with n ≥ 5), no pair among these four vertices can be adjacent in G.
have h_not_adj_m : ¬ (1 : ZMod m) = -1 ∧ ¬ Gm.Adj 1 (-1) := ⟨hne_m, hnot_m⟩ have h_not_adj_n : ¬ (1 : ZMod n) = -1 ∧ ¬ Gn.Adj 1 (-1) := ⟨hne_n, hnot_n⟩ have h_not_G_12 : ¬ G.Adj v1 v2 := by rintro ⟨-, -, h2⟩ cases h2 with | inl h => exact h_not_adj_n.1 h | inr h => exact h_not_adj_n.2 h have h_not_G_13 : ¬ G.Adj v1 v3 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_14 : ¬ G.Adj v1 v4 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_23 : ¬ G.Adj v2 v3 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_24 : ¬ G.Adj v2 v4 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_34 : ¬ G.Adj v3 v4 := by rintro ⟨-, -, h2⟩ cases h2 with | inl h => exact h_not_adj_n.1 h | inr h => exact h_not_adj_n.2 h
The four vertices v₁, v₂, v₃, v₄ are pairwise distinct.
Any two distinct vertices among {v₁, v₂, v₃, v₄} differ in at least one coordinate where one vertex has entry 1 and the other has entry -1. Since 1 ≠ -1 in ℤ/mℤ and ℤ/nℤ, the vertices cannot be equal.
uses
congr_arg,Prod.fst,Prod.sndhave hne_12 : v1 ≠ v2 := fun h => hne_n (congr_arg Prod.snd h) have hne_13 : v1 ≠ v3 := fun h => hne_m (congr_arg Prod.fst h) have hne_14 : v1 ≠ v4 := fun h => hne_m (congr_arg Prod.fst h) have hne_23 : v2 ≠ v3 := fun h => hne_m (congr_arg Prod.fst h) have hne_24 : v2 ≠ v4 := fun h => hne_m (congr_arg Prod.fst h) have hne_34 : v3 ≠ v4 := fun h => hne_n (congr_arg Prod.snd h)
The four covering indices s₁, s₂, s₃, s₄ ∈ Fin 3 are pairwise distinct.
If s_i = s_j for distinct i, j ∈ {1, 2, 3, 4}, then transitivity would give c(s_i, v_i) = c(s_i, v₀) = c(s_j, v_j) = c(s_i, v_j). Because v_i ≠ v_j, the clique condition of the equivalence subgraph would force v_i and v_j to be adjacent in G, contradicting the fact that {v₁, v₂, v₃, v₄} is an independent set.
have hs12 : s1 ≠ s2 := by intro heq have h_c : c s1 v1 = c s1 v2 := by rw [← hs1, heq, hs2] exact h_not_G_12 (hc_clique s1 v1 v2 hne_12 h_c) have hs13 : s1 ≠ s3 := by intro heq have h_c : c s1 v1 = c s1 v3 := by rw [← hs1, heq, hs3] exact h_not_G_13 (hc_clique s1 v1 v3 hne_13 h_c) have hs14 : s1 ≠ s4 := by intro heq have h_c : c s1 v1 = c s1 v4 := by rw [← hs1, heq, hs4] exact h_not_G_14 (hc_clique s1 v1 v4 hne_14 h_c) have hs23 : s2 ≠ s3 := by intro heq have h_c : c s2 v2 = c s2 v3 := by rw [← hs2, heq, hs3] exact h_not_G_23 (hc_clique s2 v2 v3 hne_23 h_c) have hs24 : s2 ≠ s4 := by intro heq have h_c : c s2 v2 = c s2 v4 := by rw [← hs2, heq, hs4] exact h_not_G_24 (hc_clique s2 v2 v4 hne_24 h_c) have hs34 : s3 ≠ s4 := by intro heq have h_c : c s3 v3 = c s3 v4 := by rw [← hs3, heq, hs4] exact h_not_G_34 (hc_clique s3 v3 v4 hne_34 h_c)
Derive a contradiction: Fin 3 cannot contain 4 pairwise distinct elements.
Using Fin.ext, the pairwise distinctness of s₁, s₂, s₃, s₄ implies that their underlying natural numbers are four distinct values, each strictly less than 3. Linear integer arithmetic closes the goal by the pigeonhole principle.
uses
Fin.exthave : s1.1 ≠ s2.1 := fun h => hs12 (Fin.ext h) have : s1.1 ≠ s3.1 := fun h => hs13 (Fin.ext h) have : s1.1 ≠ s4.1 := fun h => hs14 (Fin.ext h) have : s2.1 ≠ s3.1 := fun h => hs23 (Fin.ext h) have : s2.1 ≠ s4.1 := fun h => hs24 (Fin.ext h) have : s3.1 ≠ s4.1 := fun h => hs34 (Fin.ext h) have := s1.isLt have := s2.isLt have := s3.isLt have := s4.isLt omega
abs_le- The absolute value of an element is at most a bound if and only if the element lies between the negative bound and the bound.
abs_lt- The absolute value of an element is strictly less than a bound if and only if the element strictly lies between the negative bound and the bound.
cycle_strong_product_not_has_equivalence_cover_three_cycle_props- In a cycle of length at least 5, the vertex 0 is adjacent to 1 and -1, while 1 and -1 are distinct and not adjacent to each other.
congr_arg- Applying a function to equal arguments produces equal values.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Or.inr- Given a proof of the right disjunct, infers the disjunction.
Prod.fst- The first projection of an ordered pair.
Prod.snd- The second projection of an ordered pair.
simple_graph_cycle_power_adj_iff_of_bandwidth_lt- In a cycle power graph with bandwidth strictly less than the cycle length, two vertices are adjacent if and only if their difference is represented by a non-zero integer of absolute value at most the bandwidth.
sub_zero- Subtracting zero from an element leaves it unchanged.
zmod_intCast_eq_intCast_iff_of_abs_sub_lt- Two integers whose difference has absolute value strictly less than n have equal reductions modulo n if and only if they are equal as integers.
- The definition `simple_graph_has_equivalence_cover G t` formalizes an equivalence cover using a family of map assignments `c : Fin t → V → V`, where the fibers of each map `c s` form cliques in `G` partitioning the vertices, and every edge of `G` has its endpoints identified by at least one such map.
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 cycle_strong_product_not_has_equivalence_cover_three_cycle_props (k : ℕ) (hk : 5 ≤ k) : (simple_graph_cycle_power k 1).Adj (0 : ZMod k) 1 ∧ (simple_graph_cycle_power k 1).Adj (0 : ZMod k) (-1) ∧ (1 : ZMod k) ≠ -1 ∧ ¬ (simple_graph_cycle_power k 1).Adj (1 : ZMod k) (-1) := by have : NeZero k := ⟨by omega⟩ have hadj01 : (simple_graph_cycle_power k 1).Adj 0 1 := by rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt k 1 (by omega)] exact ⟨1, by decide, by decide, by ring⟩ have hadj0neg1 : (simple_graph_cycle_power k 1).Adj 0 (-1) := by rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt k 1 (by omega)] exact ⟨-1, by decide, by decide, by ring⟩ have hne : (1 : ZMod k) ≠ -1 := by intro h have h2 : ((2 : ℤ) : ZMod k) = ((0 : ℤ) : ZMod k) := by push_cast; linear_combination h have h_bound : |(2 : ℤ) - 0| < (k : ℤ) := by rw [sub_zero, abs_lt]; omega have h_eq : (2 : ℤ) = 0 := by rwa [zmod_intCast_eq_intCast_iff_of_abs_sub_lt k 2 0 h_bound] at h2 omega have hnot : ¬ (simple_graph_cycle_power k 1).Adj (1 : ZMod k) (-1) := by rw [simple_graph_cycle_power_adj_iff_of_bandwidth_lt k 1 (by omega)] rintro ⟨e, -, he1, he⟩ have h2 : ((e + 2 : ℤ) : ZMod k) = ((0 : ℤ) : ZMod k) := by push_cast; linear_combination -he rw [abs_le] at he1 have h_bound : |(e + 2) - 0| < (k : ℤ) := by rw [sub_zero, abs_lt]; omega have h_eq : (e + 2 : ℤ) = 0 := by rwa [zmod_intCast_eq_intCast_iff_of_abs_sub_lt k (e + 2) 0 h_bound] at h2 omega exact ⟨hadj01, hadj0neg1, hne, hnot⟩/-- For m ≥ 6 and n ≥ 5, the strong product C_m ⊠ C_n cannot be covered by 3 equivalence subgraphs. -/theorem cycle_strong_product_not_has_equivalence_cover_three (m n : ℕ) (hm : 6 ≤ m) (hn : 5 ≤ n) : ¬ simple_graph_has_equivalence_cover (simple_graph_strong_prod (simple_graph_cycle_power m 1) (simple_graph_cycle_power n 1)) 3 := by have hm5 : 5 ≤ m := by omega rcases cycle_strong_product_not_has_equivalence_cover_three_cycle_props m hm5 with ⟨hadj01_m, hadj0neg1_m, hne_m, hnot_m⟩ rcases cycle_strong_product_not_has_equivalence_cover_three_cycle_props n hn with ⟨hadj01_n, hadj0neg1_n, hne_n, hnot_n⟩ set Gm := simple_graph_cycle_power m 1 set Gn := simple_graph_cycle_power n 1 set G := simple_graph_strong_prod Gm Gn rintro ⟨c, hc_clique, hc_cov⟩ let v0 : ZMod m × ZMod n := (0, 0) let v1 : ZMod m × ZMod n := (1, 1) let v2 : ZMod m × ZMod n := (1, -1) let v3 : ZMod m × ZMod n := (-1, 1) let v4 : ZMod m × ZMod n := (-1, -1) have hadj_v0_v1 : G.Adj v0 v1 := ⟨fun h => hadj01_m.ne (congr_arg Prod.fst h), Or.inr hadj01_m, Or.inr hadj01_n⟩ have hadj_v0_v2 : G.Adj v0 v2 := ⟨fun h => hadj01_m.ne (congr_arg Prod.fst h), Or.inr hadj01_m, Or.inr hadj0neg1_n⟩ have hadj_v0_v3 : G.Adj v0 v3 := ⟨fun h => hadj0neg1_m.ne (congr_arg Prod.fst h), Or.inr hadj0neg1_m, Or.inr hadj01_n⟩ have hadj_v0_v4 : G.Adj v0 v4 := ⟨fun h => hadj0neg1_m.ne (congr_arg Prod.fst h), Or.inr hadj0neg1_m, Or.inr hadj0neg1_n⟩ rcases hc_cov v0 v1 hadj_v0_v1 with ⟨s1, hs1⟩ rcases hc_cov v0 v2 hadj_v0_v2 with ⟨s2, hs2⟩ rcases hc_cov v0 v3 hadj_v0_v3 with ⟨s3, hs3⟩ rcases hc_cov v0 v4 hadj_v0_v4 with ⟨s4, hs4⟩ have h_not_adj_m : ¬ (1 : ZMod m) = -1 ∧ ¬ Gm.Adj 1 (-1) := ⟨hne_m, hnot_m⟩ have h_not_adj_n : ¬ (1 : ZMod n) = -1 ∧ ¬ Gn.Adj 1 (-1) := ⟨hne_n, hnot_n⟩ have h_not_G_12 : ¬ G.Adj v1 v2 := by rintro ⟨-, -, h2⟩ cases h2 with | inl h => exact h_not_adj_n.1 h | inr h => exact h_not_adj_n.2 h have h_not_G_13 : ¬ G.Adj v1 v3 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_14 : ¬ G.Adj v1 v4 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_23 : ¬ G.Adj v2 v3 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_24 : ¬ G.Adj v2 v4 := by rintro ⟨-, h1, -⟩ cases h1 with | inl h => exact h_not_adj_m.1 h | inr h => exact h_not_adj_m.2 h have h_not_G_34 : ¬ G.Adj v3 v4 := by rintro ⟨-, -, h2⟩ cases h2 with | inl h => exact h_not_adj_n.1 h | inr h => exact h_not_adj_n.2 h have hne_12 : v1 ≠ v2 := fun h => hne_n (congr_arg Prod.snd h) have hne_13 : v1 ≠ v3 := fun h => hne_m (congr_arg Prod.fst h) have hne_14 : v1 ≠ v4 := fun h => hne_m (congr_arg Prod.fst h) have hne_23 : v2 ≠ v3 := fun h => hne_m (congr_arg Prod.fst h) have hne_24 : v2 ≠ v4 := fun h => hne_m (congr_arg Prod.fst h) have hne_34 : v3 ≠ v4 := fun h => hne_n (congr_arg Prod.snd h) have hs12 : s1 ≠ s2 := by intro heq have h_c : c s1 v1 = c s1 v2 := by rw [← hs1, heq, hs2] exact h_not_G_12 (hc_clique s1 v1 v2 hne_12 h_c) have hs13 : s1 ≠ s3 := by intro heq have h_c : c s1 v1 = c s1 v3 := by rw [← hs1, heq, hs3] exact h_not_G_13 (hc_clique s1 v1 v3 hne_13 h_c) have hs14 : s1 ≠ s4 := by intro heq have h_c : c s1 v1 = c s1 v4 := by rw [← hs1, heq, hs4] exact h_not_G_14 (hc_clique s1 v1 v4 hne_14 h_c) have hs23 : s2 ≠ s3 := by intro heq have h_c : c s2 v2 = c s2 v3 := by rw [← hs2, heq, hs3] exact h_not_G_23 (hc_clique s2 v2 v3 hne_23 h_c) have hs24 : s2 ≠ s4 := by intro heq have h_c : c s2 v2 = c s2 v4 := by rw [← hs2, heq, hs4] exact h_not_G_24 (hc_clique s2 v2 v4 hne_24 h_c) have hs34 : s3 ≠ s4 := by intro heq have h_c : c s3 v3 = c s3 v4 := by rw [← hs3, heq, hs4] exact h_not_G_34 (hc_clique s3 v3 v4 hne_34 h_c) have : s1.1 ≠ s2.1 := fun h => hs12 (Fin.ext h) have : s1.1 ≠ s3.1 := fun h => hs13 (Fin.ext h) have : s1.1 ≠ s4.1 := fun h => hs14 (Fin.ext h) have : s2.1 ≠ s3.1 := fun h => hs23 (Fin.ext h) have : s2.1 ≠ s4.1 := fun h => hs24 (Fin.ext h) have : s3.1 ≠ s4.1 := fun h => hs34 (Fin.ext h) have := s1.isLt have := s2.isLt have := s3.isLt have := s4.isLt omega