simple_graph_kayak_paddle_adj_zero_k
In KP(k, m, l), vertex 0 of the first cycle is adjacent to vertex k, the first vertex after it on the connecting path.
Statement
theorem simple_graph_kayak_paddle_adj_zero_k (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l) : (simple_graph_kayak_paddle k m l).Adj ⟨0, by omega⟩ ⟨k, by omega⟩
- Source
- Sanity lemma for the kayak paddle graph, arXiv:2610.18463 (The group generated by a graph's derangements), Sec. 2.4.
- Verified
- 15 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_kayak_paddleThe kayak paddle graph KP(k, m, l) (k, m ≥ 3, l ≥ 1) on N = k + m + l − 1 vertices: a cycle on 0, …, k−1, a cycle on k+l−1, …, k+l+m−2,…
The proof, explained
The kayak paddle graph is defined via SimpleGraph.fromRel from a relation that explicitly includes the directed edge between vertex 0 and vertex k. Simplifying the adjacency goal with this definition immediately satisfies the edge relation, leaving only the condition that the two vertices are distinct (0 ≠ k). This distinctness, as well as the validity of 0 and k as indices in Fin (k + m + l - 1), follows by linear arithmetic from the parameter bounds k ≥ 3, m ≥ 3, and l ≥ 1.
The indices 0 and k are strictly less than k + m + l - 1, defining valid vertices in Fin (k + m + l - 1).
Under the hypotheses k ≥ 3, m ≥ 3, and l ≥ 1, the total number of vertices k + m + l - 1 is at least 6. Linear arithmetic (`omega`) verifies that 0 < k + m + l - 1 and k < k + m + l - 1, justifying the construction of both Fin elements in the theorem statement.
(simple_graph_kayak_paddle k m l).Adj ⟨0, by omega⟩ ⟨k, by omega⟩ := by
Adjacency of vertex 0 and vertex k reduces to showing that 0 ≠ k.
The kayak paddle graph is constructed via SimpleGraph.fromRel, which defines two vertices to be adjacent if and only if they are distinct and related by the underlying relation in either direction. The definition of simple_graph_kayak_paddle explicitly includes the bridge clause (i = 0 ∧ j = k). For i = 0 and j = k, this clause is satisfied, so simplifying with the definition leaves only the loopless requirement that 0 ≠ k.
uses
simple_graph_kayak_paddlesimp [simple_graph_kayak_paddle]The vertices 0 and k are distinct (0 ≠ k).
Since k ≥ 3 by hypothesis, k is strictly positive and cannot equal 0. Linear arithmetic (`omega`) closes the remaining goal.
omega
simple_graph_kayak_paddle- The kayak paddle graph KP(k, m, l), defined as a simple graph on Fin (k + m + l - 1) by taking the symmetric, loopless closure of a relation consisting of a k-cycle, a bridge edge from 0 to k, an l-path, and an m-cycle.
- The theorem statement contains inline tactic proofs (`by omega` on line 2) to certify that 0 and k are strictly less than k + m + l - 1, which is required by Lean's type system to form valid terms of the vertex type Fin (k + m + l - 1).
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.
theorem simple_graph_kayak_paddle_adj_zero_k (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l) : (simple_graph_kayak_paddle k m l).Adj ⟨0, by omega⟩ ⟨k, by omega⟩ := by simp [simple_graph_kayak_paddle] omega