loom_grid_connected_no_mixed_column_is_path_graph
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.
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.
uses
SimpleGraph.induce_adj,SimpleGraph.fromRel_adjclassical 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
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.
uses
SimpleGraph.induce_adj,SimpleGraph.fromRel_adj,False.elim,Or.inl,Or.inrhave 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⟩
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.
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]
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.
uses
False.elim,Subtype.exthave 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
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.
uses
SimpleGraph.induce_adj,SimpleGraph.fromRel_adjhave 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⟩
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.
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
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.
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⟩
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.
uses
Fin.mk.injEq,Fin.exthave 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)
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.
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
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.
uses
Equiv.ofBijective,SimpleGraph.pathGraph_adjlet 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
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.
uses
RelIso.mkexact ⟨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.
- In the product representation `Fin r × Fin c × Bool`, a vertex `u` has row coordinate `u.1`, column coordinate `u.1.2.1` (or `u.2.1`), and boolean coordinate `u.1.2.2` (or `u.2.2`). The hypothesis that no column is mixed means that for every column `j`, all vertices in `U` located in column `j` share the exact same boolean coordinate.
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.
/-- 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)⟩⟩