triangle_free_loom_grid_connected_no_mixed_column_is_path_graph
In a triangle-free loom grid T_{r,c}, every nonempty connected vertex set with no mixed column induces a path graph.
Statement
theorem triangle_free_loom_grid_connected_no_mixed_column_is_path_graph
{r c : ℕ} (U : Set (triangle_free_loom_grid_vert r c))
(h_conn : ((triangle_free_loom_grid r c).induce U).Connected)
(h_no_mix : ∀ j : Fin c, ¬ ((∃ u ∈ U, u.1.2.1 = j ∧ u.1.2.2 = false) ∧
(∃ u ∈ U, u.1.2.1 = j ∧ u.1.2.2 = true))) :
is_path_graph ((triangle_free_loom_grid r c).induce U)- Formalizes
- arXiv:2611.09627 Lemma 3.1(a)
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- triangle_free_loom_gridThe triangle-free loom grid on the vertex type triangle_free_loom_grid_vert r c is the simple graph where two vertices u and v are…
- triangle_free_loom_grid_vertFor natural numbers r and c, triangle_free_loom_grid_vert r c is the subtype of elements v in Fin r × Fin c × Bool such that v.2.2 = false…
- 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 vertices of triangle_free_loom_grid r c:
if the subgraph induced by $U$ is connected, and for every column $j \in \text{Fin } c$, $U$ does not contain both a vertex with column $j$ and boolean component false and a vertex with column $j$ and boolean component true,
then the induced subgraph on $U$ is a path graph (isomorphic to SimpleGraph.pathGraph n for some $n : \mathbb{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
In a triangle-free loom grid, adjacent vertices are either vertical (sharing a column with opposite boolean flags) or horizontal (sharing a row with consecutive columns). Because the connected vertex set U contains no column with mixed boolean flags, all edges in the induced subgraph must be horizontal. Connectedness then forces all vertices in U to lie in the same row and have distinct column coordinates. Furthermore, connectedness ensures that these column coordinates form a contiguous interval of integers with no gaps. Mapping each vertex to its column coordinate minus the minimum column yields an adjacency-preserving bijection with the standard path graph on |U| vertices.
The vertex type of the triangle-free loom grid is a finite type. automation
By enabling classical logic and unfolding the definition of `triangle_free_loom_grid_vert r c` as a subtype of `Fin r × Fin c × Bool`, Lean establishes that the vertex type is finite (`Fintype`) via typeclass synthesis.
classical have : Fintype (triangle_free_loom_grid_vert r c) := by unfold triangle_free_loom_grid_vert infer_instance
Adjacent vertices in the induced subgraph on U cannot have the same column coordinate.
Suppose for contradiction that two adjacent vertices $u, v \in U$ share a column coordinate $j$. By the definition of the triangle-free loom grid, adjacent vertices either lie in the same row with consecutive columns, or in the same column with opposite boolean flags. Since they share column $j$, their column indices cannot be consecutive (ruled out by linear arithmetic). Thus they must form a vertical edge, meaning one vertex has boolean flag `false` and the other has `true`. But both vertices belong to $U$, contradicting the hypothesis that column $j$ has no mixed boolean values in $U$.
uses
SimpleGraph.induce_adj,SimpleGraph.fromRel_adjhave no_same_col_adj : ∀ (u v : U), ((triangle_free_loom_grid r c).induce U).Adj u v → u.1.1.2.1 ≠ v.1.1.2.1 := by intro u v h_adj h_col have hadj' := h_adj rw [SimpleGraph.induce_adj, triangle_free_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.1.2.1 refine ⟨⟨u.1, u.2, rfl, h2⟩, ⟨v.1, v.2, ?_, h3⟩⟩ exact h1.symm · omega · apply h_no_mix v.1.1.2.1 refine ⟨⟨v.1, v.2, rfl, h2⟩, ⟨u.1, u.2, ?_, h3⟩⟩ exact h1.symm · omega
Adjacent vertices in the induced subgraph lie in the same row and have consecutive column indices.
In the ambient loom grid, edges are either vertical (same column) or horizontal (same row, consecutive columns). Because the previous step established that adjacent vertices in $U$ never share a column, the vertical case is impossible. Hence any edge in the induced subgraph must be horizontal: the endpoints have identical row coordinates and their column coordinates differ by 1.
uses
SimpleGraph.induce_adj,SimpleGraph.fromRel_adj,False.elim,Or.inl,Or.inrhave adj_row_eq_and_col_diff : ∀ (u v : U), ((triangle_free_loom_grid r c).induce U).Adj u v → u.1.1.1 = v.1.1.1 ∧ (u.1.1.2.1.val + 1 = v.1.1.2.1.val ∨ v.1.1.2.1.val + 1 = u.1.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, triangle_free_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⟩
All vertices connected by a walk in the induced subgraph share the same row coordinate.
By induction on the walk: a trivial zero-length walk connects a vertex to itself, so the row is unchanged. For each step extending a walk, the adjacent vertices along the step share the same row by the previous result, so by transitivity the row coordinate is preserved along the entire walk.
have row_eq_of_walk : ∀ {u v : U}, ((triangle_free_loom_grid r c).induce U).Walk u v → u.1.1.1 = v.1.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]
Each vertex in U is uniquely determined by its column coordinate.
Suppose $u, v \in U$ have the same column coordinate. Because the induced subgraph on $U$ is connected, there is a walk between them, which implies they have the same row coordinate. Furthermore, their boolean flags must be identical, because if one were `false` and the other `true`, that column would be mixed in $U$, contradicting the hypothesis. Since row, column, and boolean values all coincide, the two vertices are identical by subtype extensionality.
uses
False.elim,Subtype.exthave col_inj : ∀ (u v : U), u.1.1.2.1 = v.1.1.2.1 → u = v := by intro u v hcol obtain ⟨p⟩ := h_conn.preconnected u v have hrow : u.1.1.1 = v.1.1.1 := row_eq_of_walk p have hbool : u.1.1.2.2 = v.1.1.2.2 := by by_contra h_diff apply h_no_mix u.1.1.2.1 revert h_diff cases hu_b : u.1.1.2.2 <;> cases hv_b : v.1.1.2.2 · intro h; exact False.elim (h rfl) · intro _ refine ⟨⟨u.1, u.2, rfl, hu_b⟩, ⟨v.1, v.2, hcol.symm, hv_b⟩⟩ · intro _ refine ⟨⟨v.1, v.2, hcol.symm, hv_b⟩, ⟨u.1, u.2, rfl, hu_b⟩⟩ · intro h; exact False.elim (h rfl) have h_val : u.1.1 = v.1.1 := by rcases u with ⟨⟨⟨u1, u2, u3⟩, hu_prop⟩, hu_mem⟩ rcases v with ⟨⟨⟨v1, v2, v3⟩, hv_prop⟩, hv_mem⟩ dsimp at * subst hrow hcol hbool rfl have h_u : u.1 = v.1 := Subtype.ext h_val exact Subtype.ext h_u
Two vertices in U are adjacent if and only if their column coordinates differ by 1.
The forward direction is already known from the horizontal-edge property. Conversely, if two vertices in $U$ have column coordinates differing by 1, they are distinct. Since $U$ is connected, a walk connects them, so they must lie in the same row. Having the same row and column difference 1 satisfies the definition of a horizontal edge in the loom grid.
uses
SimpleGraph.induce_adj,SimpleGraph.fromRel_adjhave adj_iff : ∀ (u v : U), ((triangle_free_loom_grid r c).induce U).Adj u v ↔ u.1.1.2.1.val + 1 = v.1.1.2.1.val ∨ v.1.1.2.1.val + 1 = u.1.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.1 = v.1.1.1 := row_eq_of_walk p have hne : u.1 ≠ v.1 := by intro heq have : u.1.1.2.1.val = v.1.1.2.1.val := by rw [heq] rcases h with h1 | h2 <;> omega rw [SimpleGraph.induce_adj, triangle_free_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 form a contiguous interval of natural numbers without gaps.
Suppose for contradiction that an integer $k$ between the column coordinates of $u_{lt}, u_{gt} \in U$ is not attained by any vertex in $U$. Consider the cut $A = \{u \in U \mid \text{col}(u) < k\}$. Since $u_{lt} \in A$ and $u_{gt} \notin A$ and $U$ is connected, any walk between them must cross the boundary of $A$, yielding an adjacent pair $(d_1, d_2)$ with $\text{col}(d_1) < k \le \text{col}(d_2)$. Because $k$ is not attained in $U$, we must have $\text{col}(d_2) > k$, which implies $\text{col}(d_2) - \text{col}(d_1) \ge 2$. This contradicts the fact that adjacent vertices in $U$ must have column difference exactly 1.
have col_interval : ∀ (k : ℕ) (u_lt u_gt : U), u_lt.1.1.2.1.val ≤ k → k ≤ u_gt.1.1.2.1.val → ∃ u : U, u.1.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.1.2.1.val < k := by have : u_lt.1.1.2.1.val ≠ k := fun h => h_none u_lt h omega have hgt' : k < u_gt.1.1.2.1.val := by have : u_gt.1.1.2.1.val ≠ k := fun h => h_none u_gt h omega let A : Set U := {u | u.1.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.1.2.1.val < k := hd1 have hd2_ge : k < d.snd.1.1.2.1.val := by have hnot : ¬ d.snd.1.1.2.1.val < k := hd2 have hne : d.snd.1.1.2.1.val ≠ k := fun h => h_none d.snd h omega rcases hadj with h1 | h2 <;> omega
The column coordinates in U span a range $[m, m+n-1]$, inducing a normalization map $f : U \to \text{Fin } n$.
Let $S$ be the finite set of column coordinates of vertices in $U$. Because $U$ is connected, it is nonempty, so $S$ has a minimum $m$ and a maximum $M$. Setting $n = M - m + 1$, every vertex $u \in U$ has its column coordinate in $[m, m+n-1]$. Subtracting $m$ from each column coordinate yields a well-defined index in $\text{Fin } n$.
uses
Finset.mem_image,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.1.2.1.val) Finset.univ have hSne : S.Nonempty := by obtain ⟨u0⟩ := h_conn.nonempty exact ⟨u0.1.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.1.2.1.val ∧ u.1.1.2.1.val < m + n := by intro u have hu : u.1.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.1.2.1.val - m, by have := (hrng u).2 have := (hrng u).1 omega⟩
The map $f : U \to \text{Fin } n$ is injective.
If $f(u) = f(v)$, then $\text{col}(u) - m = \text{col}(v) - m$, so $\text{col}(u) = \text{col}(v)$. By the column uniqueness property proved earlier, two vertices in $U$ with the same column coordinate must be equal.
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.1.2.1.val = v.1.1.2.1.val := by omega exact col_inj u v (Fin.ext heq)
The map $f : U \to \text{Fin } n$ is surjective.
For any target index $i \in \text{Fin } n$, the value $m + i$ lies between the minimum column $m$ (attained at $u_{\min}$) and the maximum column $M$ (attained at $u_{\max}$). By the contiguous interval property, there exists some vertex $u \in U$ with column coordinate $m + i$. Then $f(u) = (m + i) - m = i$.
have f_surj : Function.Surjective f := by intro ⟨i, hi⟩ have h1 : u_min.1.1.2.1.val ≤ m + i := by rw [hu_min]; omega have h2 : m + i ≤ u_max.1.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 induced subgraph on U is isomorphic to the standard path graph on $n$ vertices.
The bijection $e : U \simeq \text{Fin } n$ obtained from $f$ preserves adjacency: two elements of $\text{Fin } n$ are adjacent in `SimpleGraph.pathGraph n` if and only if their values differ by 1, which corresponds to the column coordinates in $U$ differing by 1. Since column difference 1 characterizes adjacency in the induced subgraph on $U$, $e$ is an edge-preserving bijection (a `RelIso`). This exhibits the induced subgraph as a path graph.
uses
Equiv.ofBijective,SimpleGraph.pathGraph_adj,RelIso.mklet 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) ↔ ((triangle_free_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.1.2.1.val + 1 = b.1.1.2.1.val ∨ b.1.1.2.1.val + 1 = a.1.1.2.1.val change (a.1.1.2.1.val - m) + 1 = (b.1.1.2.1.val - m) ∨ (b.1.1.2.1.val - m) + 1 = (a.1.1.2.1.val - m) ↔ a.1.1.2.1.val + 1 = b.1.1.2.1.val ∨ b.1.1.2.1.val + 1 = a.1.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)⟩⟩
Equiv.ofBijective- Constructs a bijection (type equivalence) from a function that is both injective and surjective.
False.elim- From a contradiction (False), any conclusion follows.
Fin.mk.injEq- Two elements of `Fin n` are equal if and only if their underlying natural values are equal.
Fin.ext- Two elements of `Fin n` are equal if their underlying natural values are equal.
Finset.mem_image- An element belongs to the image of a finite set under a function if and only if it is the image of some element in the set.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.min'_mem- The minimum element of a nonempty finite set belongs to that set.
Finset.max'_mem- The maximum element of a nonempty finite set belongs to that set.
Finset.min'_le- The minimum element 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 element of the set.
Or.inl- Proves a disjunction `P ∨ Q` given a proof of the left disjunct `P`.
Or.inr- Proves a disjunction `P ∨ Q` given a proof of the right disjunct `Q`.
RelIso.mk- Constructs a relational isomorphism between two relations from a type equivalence that preserves and reflects the relation.
SimpleGraph.fromRel_adj- In a graph defined from a binary relation, two vertices are adjacent if and only if they are distinct and the relation holds between them in at least one direction.
SimpleGraph.induce_adj- In an induced subgraph, two vertices are adjacent if and only if they are adjacent in the ambient graph.
SimpleGraph.pathGraph_adj- Two vertices in the standard path graph on `n` vertices are adjacent if and only if their indices differ by exactly 1.
Subtype.ext- Two elements of a subtype are equal if their underlying values are equal.
- Lean defines `is_path_graph G` as the existence of some `n : ℕ` such that `G` is isomorphic to `SimpleGraph.pathGraph n` via a relational isomorphism (`RelIso`).
- The discrete intermediate value property for column indices uses `SimpleGraph.Walk.exists_boundary_dart` via dot notation on the walk `p` to identify an edge crossing the cut $\{u \in U \mid \text{col}(u) < k\}$.
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 triangle-free loom grid, any nonempty connected vertex set with no mixed column induces a path graph. -/theorem triangle_free_loom_grid_connected_no_mixed_column_is_path_graph {r c : ℕ} (U : Set (triangle_free_loom_grid_vert r c)) (h_conn : ((triangle_free_loom_grid r c).induce U).Connected) (h_no_mix : ∀ j : Fin c, ¬ ((∃ u ∈ U, u.1.2.1 = j ∧ u.1.2.2 = false) ∧ (∃ u ∈ U, u.1.2.1 = j ∧ u.1.2.2 = true))) : is_path_graph ((triangle_free_loom_grid r c).induce U) := by classical have : Fintype (triangle_free_loom_grid_vert r c) := by unfold triangle_free_loom_grid_vert infer_instance have no_same_col_adj : ∀ (u v : U), ((triangle_free_loom_grid r c).induce U).Adj u v → u.1.1.2.1 ≠ v.1.1.2.1 := by intro u v h_adj h_col have hadj' := h_adj rw [SimpleGraph.induce_adj, triangle_free_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.1.2.1 refine ⟨⟨u.1, u.2, rfl, h2⟩, ⟨v.1, v.2, ?_, h3⟩⟩ exact h1.symm · omega · apply h_no_mix v.1.1.2.1 refine ⟨⟨v.1, v.2, rfl, h2⟩, ⟨u.1, u.2, ?_, h3⟩⟩ exact h1.symm · omega have adj_row_eq_and_col_diff : ∀ (u v : U), ((triangle_free_loom_grid r c).induce U).Adj u v → u.1.1.1 = v.1.1.1 ∧ (u.1.1.2.1.val + 1 = v.1.1.2.1.val ∨ v.1.1.2.1.val + 1 = u.1.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, triangle_free_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}, ((triangle_free_loom_grid r c).induce U).Walk u v → u.1.1.1 = v.1.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.1.2.1 = v.1.1.2.1 → u = v := by intro u v hcol obtain ⟨p⟩ := h_conn.preconnected u v have hrow : u.1.1.1 = v.1.1.1 := row_eq_of_walk p have hbool : u.1.1.2.2 = v.1.1.2.2 := by by_contra h_diff apply h_no_mix u.1.1.2.1 revert h_diff cases hu_b : u.1.1.2.2 <;> cases hv_b : v.1.1.2.2 · intro h; exact False.elim (h rfl) · intro _ refine ⟨⟨u.1, u.2, rfl, hu_b⟩, ⟨v.1, v.2, hcol.symm, hv_b⟩⟩ · intro _ refine ⟨⟨v.1, v.2, hcol.symm, hv_b⟩, ⟨u.1, u.2, rfl, hu_b⟩⟩ · intro h; exact False.elim (h rfl) have h_val : u.1.1 = v.1.1 := by rcases u with ⟨⟨⟨u1, u2, u3⟩, hu_prop⟩, hu_mem⟩ rcases v with ⟨⟨⟨v1, v2, v3⟩, hv_prop⟩, hv_mem⟩ dsimp at * subst hrow hcol hbool rfl have h_u : u.1 = v.1 := Subtype.ext h_val exact Subtype.ext h_u have adj_iff : ∀ (u v : U), ((triangle_free_loom_grid r c).induce U).Adj u v ↔ u.1.1.2.1.val + 1 = v.1.1.2.1.val ∨ v.1.1.2.1.val + 1 = u.1.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.1 = v.1.1.1 := row_eq_of_walk p have hne : u.1 ≠ v.1 := by intro heq have : u.1.1.2.1.val = v.1.1.2.1.val := by rw [heq] rcases h with h1 | h2 <;> omega rw [SimpleGraph.induce_adj, triangle_free_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.1.2.1.val ≤ k → k ≤ u_gt.1.1.2.1.val → ∃ u : U, u.1.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.1.2.1.val < k := by have : u_lt.1.1.2.1.val ≠ k := fun h => h_none u_lt h omega have hgt' : k < u_gt.1.1.2.1.val := by have : u_gt.1.1.2.1.val ≠ k := fun h => h_none u_gt h omega let A : Set U := {u | u.1.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.1.2.1.val < k := hd1 have hd2_ge : k < d.snd.1.1.2.1.val := by have hnot : ¬ d.snd.1.1.2.1.val < k := hd2 have hne : d.snd.1.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.1.2.1.val) Finset.univ have hSne : S.Nonempty := by obtain ⟨u0⟩ := h_conn.nonempty exact ⟨u0.1.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.1.2.1.val ∧ u.1.1.2.1.val < m + n := by intro u have hu : u.1.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.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.1.2.1.val = v.1.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.1.2.1.val ≤ m + i := by rw [hu_min]; omega have h2 : m + i ≤ u_max.1.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) ↔ ((triangle_free_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.1.2.1.val + 1 = b.1.1.2.1.val ∨ b.1.1.2.1.val + 1 = a.1.1.2.1.val change (a.1.1.2.1.val - m) + 1 = (b.1.1.2.1.val - m) ∨ (b.1.1.2.1.val - m) + 1 = (a.1.1.2.1.val - m) ↔ a.1.1.2.1.val + 1 = b.1.1.2.1.val ∨ b.1.1.2.1.val + 1 = a.1.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)⟩⟩