AFTD Auto-Formalizing Theoretical Domains

loom_grid_connected_no_mixed_column_is_path_graph

theoremverifiedformalization

In a loom grid B_{r,c}, every nonempty connected vertex set with no mixed column induces a path graph.

Statement

theorem loom_grid_connected_no_mixed_column_is_path_graph
    {r c : ℕ} (U : Set (Fin r × Fin c × Bool))
    (h_conn : ((loom_grid r c).induce U).Connected)
    (h_no_mix : ∀ j : Fin c, ¬ ((∃ i : Fin r, (i, j, false) ∈ U) ∧ (∃ i : Fin r, (i, j, true) ∈ U))) :
    is_path_graph ((loom_grid r c).induce U)
Formalizes
arXiv:2611.09627 Lemma 3.1(a)
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • loom_gridThe loom grid B_{r,c} has vertex set [r] × [c] × {-, +}, where within each column all pairs on opposite sides are adjacent, and between…
  • is_path_graphA simple graph is a path graph if it is isomorphic to a standard path graph on n vertices for some n.

Read back from the Lean

For any natural numbers r and c, and any subset U of Fin r × Fin c × Bool, if: 1. The subgraph of loom_grid r c induced by U is connected (SimpleGraph.Connected), and 2. For every column j : Fin c, it is not the case that there exist both an i : Fin r such that (i, j, false) ∈ U and an i' : Fin r such that (i', j, true) ∈ U (i.e., no column in U contains vertices with both boolean values), then the induced subgraph (loom_grid r c).induce U is a path graph, meaning there exists some natural number n such that it is isomorphic to SimpleGraph.pathGraph 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

The proof shows that any nonempty connected vertex set U in a loom grid without mixed columns induces a path graph. First, the absence of mixed columns forbids vertical (within-column) edges in U, forcing all edges and thus all walks in U to lie in the same row, so vertices in U are uniquely determined by their column coordinates. Two vertices in U are adjacent if and only if their column indices differ by 1, and connectedness ensures the set of column indices forms an interval with no gaps. Shifting the column indices by the minimum column yields an isomorphism between the induced subgraph on U and the path graph on |U| vertices.

  1. Adjacent vertices in U cannot belong to the same column.

    Assume for contradiction that two adjacent vertices u, v ∈ U share the same column. By the definition of edges in the loom grid, within-column edges must connect a vertex with boolean value false to one with true. This implies their shared column contains both a false vertex and a true vertex in U, contradicting the hypothesis h_no_mix. The other edge type in the loom grid requires column indices to differ by 1, which contradicts the columns being equal.

    lines 7–30

    uses SimpleGraph.induce_adj, SimpleGraph.fromRel_adj

      classical
      have no_same_col_adj : ∀ (u v : U), ((loom_grid r c).induce U).Adj u v → u.1.2.1 ≠ v.1.2.1 := by
        intro u v h_adj h_col
        have hadj' := h_adj
        rw [SimpleGraph.induce_adj, loom_grid, SimpleGraph.fromRel_adj] at hadj'
        rcases hadj'.2 with (⟨h1, h2, h3⟩ | ⟨h1, h2⟩) | (⟨h1, h2, h3⟩ | ⟨h1, h2⟩)
        · apply h_no_mix u.1.2.1
          refine ⟨⟨u.1.1, ?_⟩, ⟨v.1.1, ?_⟩⟩
          · have : (u.1.1, u.1.2.1, false) = u.1 := by
              rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [h2]
            exact this ▸ u.2
          · have : (v.1.1, u.1.2.1, true) = v.1 := by
              rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [← h1, h3]
            exact this ▸ v.2
        · omega
        · apply h_no_mix v.1.2.1
          refine ⟨⟨v.1.1, ?_⟩, ⟨u.1.1, ?_⟩⟩
          · have : (v.1.1, v.1.2.1, false) = v.1 := by
              rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [h2]
            exact this ▸ v.2
          · have : (u.1.1, v.1.2.1, true) = u.1 := by
              rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [← h1, h3]
            exact this ▸ u.2
        · omega
  2. Adjacent vertices in U must lie in the same row and in adjacent columns.

    By no_same_col_adj, adjacent vertices cannot share a column. Unfolding the definition of adjacency in the loom grid, the within-column edge cases are eliminated via False.elim. Hence, any edge in the induced subgraph must be a horizontal edge, meaning u and v have identical row coordinates and their column coordinates differ by exactly 1.

    lines 32–42

    uses SimpleGraph.induce_adj, SimpleGraph.fromRel_adj, False.elim, Or.inl, Or.inr

      have adj_row_eq_and_col_diff : ∀ (u v : U), ((loom_grid r c).induce U).Adj u v →
          u.1.1 = v.1.1 ∧ (u.1.2.1.val + 1 = v.1.2.1.val ∨ v.1.2.1.val + 1 = u.1.2.1.val) := by
        intro u v h_adj
        have hcol := no_same_col_adj u v h_adj
        have hadj' := h_adj
        rw [SimpleGraph.induce_adj, loom_grid, SimpleGraph.fromRel_adj] at hadj'
        rcases hadj'.2 with (⟨h1, -⟩ | ⟨h1, h2⟩) | (⟨h1, -⟩ | ⟨h1, h2⟩)
        · exact False.elim (hcol h1)
        · exact ⟨h1, Or.inl h2⟩
        · exact False.elim (hcol h1.symm)
        · exact ⟨h1.symm, Or.inr h2⟩
  3. Every walk in the induced subgraph stays entirely within a single row.

    This is proved by induction on the walk. A walk of length zero (nil) starts and ends at the same vertex, so the row coordinates trivially match. In the inductive step (cons), the first edge connects two vertices in the same row by adj_row_eq_and_col_diff, and the rest of the walk preserves the row by the induction hypothesis.

    lines 44–50

      have row_eq_of_walk : ∀ {u v : U}, ((loom_grid r c).induce U).Walk u v → u.1.1 = v.1.1 := by
        intro u v p
        induction p with
        | nil => rfl
        | cons hadj p ih =>
          have := adj_row_eq_and_col_diff _ _ hadj
          rw [this.1, ih]
  4. The column coordinate uniquely determines the vertex in U.

    Suppose two vertices u, v ∈ U have identical column coordinates. Since the induced subgraph on U is connected, there is a walk between u and v, which by row_eq_of_walk forces them to share the same row. If their boolean coordinates differed, their column would contain both false and true in U, contradicting h_no_mix; thus their boolean coordinates must also agree. Having identical row, column, and boolean components, u and v are equal as subtype elements by Subtype.ext.

    lines 52–84

    uses False.elim, Subtype.ext

      have col_inj : ∀ (u v : U), u.1.2.1 = v.1.2.1 → u = v := by
        intro u v hcol
        obtain ⟨p⟩ := h_conn.preconnected u v
        have hrow : u.1.1 = v.1.1 := row_eq_of_walk p
        have hbool : u.1.2.2 = v.1.2.2 := by
          by_contra h_diff
          apply h_no_mix u.1.2.1
          revert h_diff
          cases hu_b : u.1.2.2 <;> cases hv_b : v.1.2.2
          · intro h; exact False.elim (h rfl)
          · intro _
            refine ⟨⟨u.1.1, ?_⟩, ⟨v.1.1, ?_⟩⟩
            · have : (u.1.1, u.1.2.1, false) = u.1 := by
                rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [hu_b]
              exact this ▸ u.2
            · have : (v.1.1, u.1.2.1, true) = v.1 := by
                rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [← hcol, hv_b]
              exact this ▸ v.2
          · intro _
            refine ⟨⟨v.1.1, ?_⟩, ⟨u.1.1, ?_⟩⟩
            · have : (v.1.1, u.1.2.1, false) = v.1 := by
                rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [← hcol, hv_b]
              exact this ▸ v.2
            · have : (u.1.1, u.1.2.1, true) = u.1 := by
                rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [hu_b]
              exact this ▸ u.2
          · intro h; exact False.elim (h rfl)
        apply Subtype.ext
        rcases u with ⟨⟨u1, u21, u22⟩, hu⟩
        rcases v with ⟨⟨v1, v21, v22⟩, hv⟩
        dsimp at *
        subst hrow hcol hbool
        rfl
  5. Two vertices in U are adjacent if and only if their column coordinates differ by exactly 1.

    The forward direction is given by adj_row_eq_and_col_diff. Conversely, if their column coordinates differ by 1, the two vertices are distinct. Because U is connected, there is a walk between them, which implies by row_eq_of_walk that they lie in the same row. Having the same row and columns differing by 1 satisfies the definition of a horizontal edge in the loom grid, establishing adjacency in the induced subgraph.

    lines 86–102

    uses SimpleGraph.induce_adj, SimpleGraph.fromRel_adj

      have adj_iff : ∀ (u v : U), ((loom_grid r c).induce U).Adj u v ↔
          u.1.2.1.val + 1 = v.1.2.1.val ∨ v.1.2.1.val + 1 = u.1.2.1.val := by
        intro u v
        constructor
        · exact fun h => (adj_row_eq_and_col_diff u v h).2
        · intro h
          obtain ⟨p⟩ := h_conn.preconnected u v
          have hrow : u.1.1 = v.1.1 := row_eq_of_walk p
          have hne : u.1 ≠ v.1 := by
            intro heq
            have : u.1.2.1.val = v.1.2.1.val := by rw [heq]
            rcases h with h1 | h2 <;> omega
          rw [SimpleGraph.induce_adj, loom_grid, SimpleGraph.fromRel_adj]
          refine ⟨hne, ?_⟩
          rcases h with h1 | h2
          · left; right; exact ⟨hrow, h1⟩
          · right; right; exact ⟨hrow.symm, h2⟩
  6. The column coordinates of vertices in U contain no gaps between the minimum and maximum column.

    Suppose for contradiction that an intermediate column index k between the column of u_lt and u_gt contains no vertex in U. Dividing U into the cut A of vertices with column < k and its complement, u_lt is in A while u_gt is not. Any path between them in the connected graph must cross the cut along some boundary edge. The endpoints of this boundary edge are adjacent, so their column indices differ by 1 by adj_iff. But since no vertex in U has column k, the endpoint in A has column < k and the other endpoint has column > k, meaning their columns differ by at least 2, a contradiction.

    lines 104–127

      have col_interval : ∀ (k : ℕ) (u_lt u_gt : U),
          u_lt.1.2.1.val ≤ k → k ≤ u_gt.1.2.1.val → ∃ u : U, u.1.2.1.val = k := by
        intro k u_lt u_gt hlt hgt
        by_contra h_none
        push Not at h_none
        have hlt' : u_lt.1.2.1.val < k := by
          have : u_lt.1.2.1.val ≠ k := fun h => h_none u_lt h
          omega
        have hgt' : k < u_gt.1.2.1.val := by
          have : u_gt.1.2.1.val ≠ k := fun h => h_none u_gt h
          omega
        let A : Set U := {u | u.1.2.1.val < k}
        have hA_lt : u_lt ∈ A := hlt'
        have hA_gt : u_gt ∉ A := by simp [A]; omega
        obtain ⟨p⟩ := h_conn.preconnected u_lt u_gt
        obtain ⟨d, -, hd1, hd2⟩ := p.exists_boundary_dart A hA_lt hA_gt
        have hadj := d.adj
        rw [adj_iff] at hadj
        have hd1_lt : d.fst.1.2.1.val < k := hd1
        have hd2_ge : k < d.snd.1.2.1.val := by
          have hnot : ¬ d.snd.1.2.1.val < k := hd2
          have hne : d.snd.1.2.1.val ≠ k := fun h => h_none d.snd h
          omega
        rcases hadj with h1 | h2 <;> omega
  7. The column coordinates form a nonempty finite set with minimum m and maximum M, defining a range of n = M - m + 1 consecutive columns and a coordinate map f : U → Fin n.

    Let S be the image of U under the column projection. Since U is connected and hence nonempty, S has a minimum m and maximum M, attained at vertices u_min and u_max. Setting n = M - m + 1, every vertex in U has column value in [m, M], so mapping each vertex u to u.1.2.1.val - m defines a valid function f : U → Fin n.

    lines 129–150

    uses Finset.mem_univ, Finset.min'_mem, Finset.max'_mem, Finset.min'_le, Finset.le_max'

      let S : Finset ℕ := Finset.image (fun u : U => u.1.2.1.val) Finset.univ
      have hSne : S.Nonempty := by
        obtain ⟨u0⟩ := h_conn.nonempty
        exact ⟨u0.1.2.1.val, Finset.mem_image.2 ⟨u0, Finset.mem_univ _, rfl⟩⟩
      let m := S.min' hSne
      let M := S.max' hSne
      obtain ⟨u_min, -, hu_min⟩ := Finset.mem_image.1 (Finset.min'_mem S hSne)
      obtain ⟨u_max, -, hu_max⟩ := Finset.mem_image.1 (Finset.max'_mem S hSne)
      have hmle : m ≤ M := Finset.min'_le S M (Finset.max'_mem S hSne)
      let n := M - m + 1
      have hrng : ∀ u : U, m ≤ u.1.2.1.val ∧ u.1.2.1.val < m + n := by
        intro u
        have hu : u.1.2.1.val ∈ S := Finset.mem_image.2 ⟨u, Finset.mem_univ _, rfl⟩
        have hm := Finset.min'_le S _ hu
        have hM := Finset.le_max' S _ hu
        exact ⟨hm, by omega⟩
    
      let f : U → Fin n := fun u => ⟨u.1.2.1.val - m, by
        have := (hrng u).2
        have := (hrng u).1
        omega⟩
    
  8. The coordinate map f is injective.

    If f(u) = f(v), then u and v have equal column indices after adding m back. By col_inj, having the same column coordinate implies u = v.

    lines 151–157

    uses Fin.mk.injEq, Fin.ext

      have f_inj : Function.Injective f := by
        intro u v huv
        simp only [f, Fin.mk.injEq] at huv
        have hu := (hrng u).1
        have hv := (hrng v).1
        have heq : u.1.2.1.val = v.1.2.1.val := by omega
        exact col_inj u v (Fin.ext heq)
  9. The coordinate map f is surjective.

    For any index i in Fin n, the target column m + i lies between m and M. By col_interval applied between u_min and u_max, there exists a vertex u in U whose column index is exactly m + i, which means f(u) = i.

    lines 159–167

      have f_surj : Function.Surjective f := by
        intro ⟨i, hi⟩
        have h1 : u_min.1.2.1.val ≤ m + i := by rw [hu_min]; omega
        have h2 : m + i ≤ u_max.1.2.1.val := by rw [hu_max]; omega
        obtain ⟨u, hu⟩ := col_interval (m + i) u_min u_max h1 h2
        refine ⟨u, ?_⟩
        ext
        simp only [f]
        omega
  10. The bijection e induced by f preserves adjacency, giving an isomorphism with the path graph on n vertices.

    Since f is bijective, Equiv.ofBijective promotes it to an equivalence e : U ≃ Fin n. In the path graph on n vertices, adjacency means values differ by 1. Because e shifts column coordinates by -m, values e(a) and e(b) differ by 1 if and only if the original column coordinates of a and b differ by 1, which by adj_iff is equivalent to a and b being adjacent in the induced subgraph on U.

    lines 169–182

    uses Equiv.ofBijective, SimpleGraph.pathGraph_adj

      let e : U ≃ Fin n := Equiv.ofBijective f ⟨f_inj, f_surj⟩
      have e_adj : ∀ a b : U, (SimpleGraph.pathGraph n).Adj (e a) (e b) ↔
          ((loom_grid r c).induce U).Adj a b := by
        intro a b
        rw [SimpleGraph.pathGraph_adj, adj_iff]
        have ha := (hrng a).1
        have hb := (hrng b).1
        change (e a).val + 1 = (e b).val ∨ (e b).val + 1 = (e a).val ↔
          a.1.2.1.val + 1 = b.1.2.1.val ∨ b.1.2.1.val + 1 = a.1.2.1.val
        change (a.1.2.1.val - m) + 1 = (b.1.2.1.val - m) ∨ (b.1.2.1.val - m) + 1 = (a.1.2.1.val - m) ↔
          a.1.2.1.val + 1 = b.1.2.1.val ∨ b.1.2.1.val + 1 = a.1.2.1.val
        constructor
        · rintro (h | h) <;> [left; right] <;> omega
        · rintro (h | h) <;> [left; right] <;> omega
  11. The induced subgraph on U is a path graph.

    Packaging the vertex equivalence e and the adjacency equivalence e_adj into a RelIso witnesses that the induced subgraph on U is isomorphic to SimpleGraph.pathGraph n, satisfying the definition of is_path_graph.

    line 184

    uses RelIso.mk

      exact ⟨n, ⟨RelIso.mk e (fun {a b} => e_adj a b)⟩⟩
SimpleGraph.induce_adj
In an induced subgraph, two vertices are adjacent if and only if their underlying vertices are adjacent in the ambient graph.
SimpleGraph.fromRel_adj
Two vertices are adjacent in the simple graph generated by a relation r if and only if they are distinct and related by r in either direction.
False.elim
From a contradiction (False), any conclusion follows.
Or.inl
A disjunction a ∨ b holds if its left disjunct a holds.
Or.inr
A disjunction a ∨ b holds if its right disjunct b holds.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Finset.mem_univ
Every element of a finite type belongs to the universal finset of that type.
Finset.min'_mem
The minimum of a nonempty finite set belongs to that set.
Finset.max'_mem
The maximum of a nonempty finite set belongs to that set.
Finset.min'_le
The minimum of a finite set is less than or equal to any element in the set.
Finset.le_max'
Any element in a finite set is less than or equal to the maximum of the set.
Fin.mk.injEq
Two elements of Fin n are equal if and only if their underlying natural number values are equal.
Fin.ext
Two elements of Fin n are equal if their numerical values are equal.
Equiv.ofBijective
A bijective function between types yields an equivalence (bijection).
SimpleGraph.pathGraph_adj
In the path graph on n vertices, two vertices are adjacent if and only if their indices differ by exactly 1.
RelIso.mk
An equivalence between vertex sets that preserves and reflects adjacency defines an isomorphism of graphs.

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

/-- In a loom grid, any nonempty connected vertex set with no mixed column induces a path graph. -/theorem loom_grid_connected_no_mixed_column_is_path_graph    {r c : ℕ} (U : Set (Fin r × Fin c × Bool))    (h_conn : ((loom_grid r c).induce U).Connected)    (h_no_mix : ∀ j : Fin c, ¬ ((∃ i : Fin r, (i, j, false) ∈ U) ∧ (∃ i : Fin r, (i, j, true) ∈ U))) :    is_path_graph ((loom_grid r c).induce U) := by  classical  have no_same_col_adj : ∀ (u v : U), ((loom_grid r c).induce U).Adj u v → u.1.2.1 ≠ v.1.2.1 := by    intro u v h_adj h_col    have hadj' := h_adj    rw [SimpleGraph.induce_adj, loom_grid, SimpleGraph.fromRel_adj] at hadj'    rcases hadj'.2 with (⟨h1, h2, h3⟩ | ⟨h1, h2⟩) | (⟨h1, h2, h3⟩ | ⟨h1, h2⟩)    · apply h_no_mix u.1.2.1      refine ⟨⟨u.1.1, ?_⟩, ⟨v.1.1, ?_⟩⟩      · have : (u.1.1, u.1.2.1, false) = u.1 := by          rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [h2]        exact this ▸ u.2      · have : (v.1.1, u.1.2.1, true) = v.1 := by          rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [← h1, h3]        exact this ▸ v.2    · omega    · apply h_no_mix v.1.2.1      refine ⟨⟨v.1.1, ?_⟩, ⟨u.1.1, ?_⟩⟩      · have : (v.1.1, v.1.2.1, false) = v.1 := by          rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [h2]        exact this ▸ v.2      · have : (u.1.1, v.1.2.1, true) = u.1 := by          rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [← h1, h3]        exact this ▸ u.2    · omega  have adj_row_eq_and_col_diff : ∀ (u v : U), ((loom_grid r c).induce U).Adj u v →      u.1.1 = v.1.1 ∧ (u.1.2.1.val + 1 = v.1.2.1.val ∨ v.1.2.1.val + 1 = u.1.2.1.val) := by    intro u v h_adj    have hcol := no_same_col_adj u v h_adj    have hadj' := h_adj    rw [SimpleGraph.induce_adj, loom_grid, SimpleGraph.fromRel_adj] at hadj'    rcases hadj'.2 with (⟨h1, -⟩ | ⟨h1, h2⟩) | (⟨h1, -⟩ | ⟨h1, h2⟩)    · exact False.elim (hcol h1)    · exact ⟨h1, Or.inl h2⟩    · exact False.elim (hcol h1.symm)    · exact ⟨h1.symm, Or.inr h2⟩  have row_eq_of_walk : ∀ {u v : U}, ((loom_grid r c).induce U).Walk u v → u.1.1 = v.1.1 := by    intro u v p    induction p with    | nil => rfl    | cons hadj p ih =>      have := adj_row_eq_and_col_diff _ _ hadj      rw [this.1, ih]  have col_inj : ∀ (u v : U), u.1.2.1 = v.1.2.1 → u = v := by    intro u v hcol    obtain ⟨p⟩ := h_conn.preconnected u v    have hrow : u.1.1 = v.1.1 := row_eq_of_walk p    have hbool : u.1.2.2 = v.1.2.2 := by      by_contra h_diff      apply h_no_mix u.1.2.1      revert h_diff      cases hu_b : u.1.2.2 <;> cases hv_b : v.1.2.2      · intro h; exact False.elim (h rfl)      · intro _        refine ⟨⟨u.1.1, ?_⟩, ⟨v.1.1, ?_⟩⟩        · have : (u.1.1, u.1.2.1, false) = u.1 := by            rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [hu_b]          exact this ▸ u.2        · have : (v.1.1, u.1.2.1, true) = v.1 := by            rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [← hcol, hv_b]          exact this ▸ v.2      · intro _        refine ⟨⟨v.1.1, ?_⟩, ⟨u.1.1, ?_⟩⟩        · have : (v.1.1, u.1.2.1, false) = v.1 := by            rcases v with ⟨⟨v1, v21, v22⟩, hv⟩; dsimp at *; rw [← hcol, hv_b]          exact this ▸ v.2        · have : (u.1.1, u.1.2.1, true) = u.1 := by            rcases u with ⟨⟨u1, u21, u22⟩, hu⟩; dsimp at *; rw [hu_b]          exact this ▸ u.2      · intro h; exact False.elim (h rfl)    apply Subtype.ext    rcases u with ⟨⟨u1, u21, u22⟩, hu⟩    rcases v with ⟨⟨v1, v21, v22⟩, hv⟩    dsimp at *    subst hrow hcol hbool    rfl  have adj_iff : ∀ (u v : U), ((loom_grid r c).induce U).Adj u v ↔      u.1.2.1.val + 1 = v.1.2.1.val ∨ v.1.2.1.val + 1 = u.1.2.1.val := by    intro u v    constructor    · exact fun h => (adj_row_eq_and_col_diff u v h).2    · intro h      obtain ⟨p⟩ := h_conn.preconnected u v      have hrow : u.1.1 = v.1.1 := row_eq_of_walk p      have hne : u.1 ≠ v.1 := by        intro heq        have : u.1.2.1.val = v.1.2.1.val := by rw [heq]        rcases h with h1 | h2 <;> omega      rw [SimpleGraph.induce_adj, loom_grid, SimpleGraph.fromRel_adj]      refine ⟨hne, ?_⟩      rcases h with h1 | h2      · left; right; exact ⟨hrow, h1⟩      · right; right; exact ⟨hrow.symm, h2⟩  have col_interval : ∀ (k : ℕ) (u_lt u_gt : U),      u_lt.1.2.1.val ≤ k → k ≤ u_gt.1.2.1.val → ∃ u : U, u.1.2.1.val = k := by    intro k u_lt u_gt hlt hgt    by_contra h_none    push Not at h_none    have hlt' : u_lt.1.2.1.val < k := by      have : u_lt.1.2.1.val ≠ k := fun h => h_none u_lt h      omega    have hgt' : k < u_gt.1.2.1.val := by      have : u_gt.1.2.1.val ≠ k := fun h => h_none u_gt h      omega    let A : Set U := {u | u.1.2.1.val < k}    have hA_lt : u_lt ∈ A := hlt'    have hA_gt : u_gt ∉ A := by simp [A]; omega    obtain ⟨p⟩ := h_conn.preconnected u_lt u_gt    obtain ⟨d, -, hd1, hd2⟩ := p.exists_boundary_dart A hA_lt hA_gt    have hadj := d.adj    rw [adj_iff] at hadj    have hd1_lt : d.fst.1.2.1.val < k := hd1    have hd2_ge : k < d.snd.1.2.1.val := by      have hnot : ¬ d.snd.1.2.1.val < k := hd2      have hne : d.snd.1.2.1.val ≠ k := fun h => h_none d.snd h      omega    rcases hadj with h1 | h2 <;> omega  let S : Finset ℕ := Finset.image (fun u : U => u.1.2.1.val) Finset.univ  have hSne : S.Nonempty := by    obtain ⟨u0⟩ := h_conn.nonempty    exact ⟨u0.1.2.1.val, Finset.mem_image.2 ⟨u0, Finset.mem_univ _, rfl⟩⟩  let m := S.min' hSne  let M := S.max' hSne  obtain ⟨u_min, -, hu_min⟩ := Finset.mem_image.1 (Finset.min'_mem S hSne)  obtain ⟨u_max, -, hu_max⟩ := Finset.mem_image.1 (Finset.max'_mem S hSne)  have hmle : m ≤ M := Finset.min'_le S M (Finset.max'_mem S hSne)  let n := M - m + 1  have hrng : ∀ u : U, m ≤ u.1.2.1.val ∧ u.1.2.1.val < m + n := by    intro u    have hu : u.1.2.1.val ∈ S := Finset.mem_image.2 ⟨u, Finset.mem_univ _, rfl⟩    have hm := Finset.min'_le S _ hu    have hM := Finset.le_max' S _ hu    exact ⟨hm, by omega⟩  let f : U → Fin n := fun u => ⟨u.1.2.1.val - m, by    have := (hrng u).2    have := (hrng u).1    omega⟩  have f_inj : Function.Injective f := by    intro u v huv    simp only [f, Fin.mk.injEq] at huv    have hu := (hrng u).1    have hv := (hrng v).1    have heq : u.1.2.1.val = v.1.2.1.val := by omega    exact col_inj u v (Fin.ext heq)  have f_surj : Function.Surjective f := by    intro ⟨i, hi⟩    have h1 : u_min.1.2.1.val ≤ m + i := by rw [hu_min]; omega    have h2 : m + i ≤ u_max.1.2.1.val := by rw [hu_max]; omega    obtain ⟨u, hu⟩ := col_interval (m + i) u_min u_max h1 h2    refine ⟨u, ?_⟩    ext    simp only [f]    omega  let e : U ≃ Fin n := Equiv.ofBijective f ⟨f_inj, f_surj⟩  have e_adj : ∀ a b : U, (SimpleGraph.pathGraph n).Adj (e a) (e b) ↔      ((loom_grid r c).induce U).Adj a b := by    intro a b    rw [SimpleGraph.pathGraph_adj, adj_iff]    have ha := (hrng a).1    have hb := (hrng b).1    change (e a).val + 1 = (e b).val ∨ (e b).val + 1 = (e a).val ↔      a.1.2.1.val + 1 = b.1.2.1.val ∨ b.1.2.1.val + 1 = a.1.2.1.val    change (a.1.2.1.val - m) + 1 = (b.1.2.1.val - m) ∨ (b.1.2.1.val - m) + 1 = (a.1.2.1.val - m) ↔      a.1.2.1.val + 1 = b.1.2.1.val ∨ b.1.2.1.val + 1 = a.1.2.1.val    constructor    · rintro (h | h) <;> [left; right] <;> omega    · rintro (h | h) <;> [left; right] <;> omega  exact ⟨n, ⟨RelIso.mk e (fun {a b} => e_adj a b)⟩⟩
See it in the graphDiscuss this resultChallenge it