AFTD Auto-Formalizing Theoretical Domains

simple_graph_kayak_paddle_adj_zero_k

theoremverified

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.

  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.

    line 2

        (simple_graph_kayak_paddle k m l).Adj ⟨0, by omega⟩ ⟨k, by omega⟩ := by
  2. 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.

    line 3

    uses simple_graph_kayak_paddle

      simp [simple_graph_kayak_paddle]
  3. 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.

    line 4

      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.

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

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