AFTD Auto-Formalizing Theoretical Domains

cycle_strong_product_not_has_equivalence_cover_three

theoremverifiedoriginal

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

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.

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

    lines 6–12

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt

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

    lines 13–21

    uses sub_zero, abs_lt, zmod_intCast_eq_intCast_iff_of_abs_sub_lt

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

    lines 22–33

    uses simple_graph_cycle_power_adj_iff_of_bandwidth_lt, abs_le, sub_zero, abs_lt, zmod_intCast_eq_intCast_iff_of_abs_sub_lt

      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⟩
  4. 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, ·).

    lines 40–48

    uses cycle_strong_product_not_has_equivalence_cover_three_cycle_props

      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⟩
  5. 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).

    lines 49–61

    uses congr_arg, Prod.fst, Or.inr

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

    lines 62–65

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

    lines 66–97

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

    lines 98–103

    uses congr_arg, Prod.fst, Prod.snd

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

    lines 104–127

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

    lines 128–138

    uses Fin.ext

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

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