AFTD Auto-Formalizing Theoretical Domains

kayak_paddle_hop_maps_first_cycle

theoremverified

In KP(k, m, l) with k even, every hop maps the vertex set of the first cycle (the k-cycle) into itself.

Statement

theorem kayak_paddle_hop_maps_first_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l)
    (he : Even k) (h : Equiv.Perm (Fin (k + m + l - 1)))
    (hh : simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) (v : Fin (k + m + l - 1))
    (hv : (v : ℕ) < k) : (h v : ℕ) < k
Source
Serves kayak_paddle_leap_group_ne_of_even_cycle; arXiv:2610.18463 (The group generated by a graph's derangements), Question 2.20 (list entry OP-301).
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.
  • 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,…
Used by 1

The proof, explained

The kayak paddle graph KP(k, m, l) consists of a k-cycle, an m-cycle, and a path of length l connecting them, attached to the first cycle at vertex 0. The remaining vertices 1, ..., k-1 of the first cycle form an open path whose neighbors remain inside the cycle. To show every hop h preserves the cycle, it suffices to show h(0) < k, since hops from any other cycle vertex cannot escape. If h(0) ≥ k, the inverse permutation g = h⁻¹ must preserve the open path and shift every vertex by ±1, toggling parity. But for even k, the open path has k/2 odd vertices and only k/2 - 1 even vertices, making an injective parity-reversing map impossible.

  1. Any neighbor in KP(k, m, l) of a vertex in the open path T = {w | 0 < w < k} belongs to the first cycle (has index < k).

    By definition of the kayak paddle graph, the only vertex in the first cycle with edges outside that cycle is the junction vertex 0, which connects to the path at vertex k. Since 0 < w < k, w cannot be 0, so every edge incident to w must lead to another vertex in the first cycle. Linear arithmetic (omega) verifies that all clauses of the adjacency relation outside the first cycle require one endpoint to be at least k, which is incompatible with w < k and w > 0.

    lines 6–10

    uses SimpleGraph.fromRel_adj

      have stepA : ∀ u w : Fin (k + m + l - 1), 0 < (w : ℕ) → (w : ℕ) < k →
          (simple_graph_kayak_paddle k m l).Adj w u → (u : ℕ) < k := by
        intro u w hw hwk hadj
        simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj
        omega
  2. Adjacency between any two vertices in the open path T is standard path adjacency: |u - w| = 1.

    Adjacent vertices in the first cycle must satisfy w ≡ u + 1 (mod k) or u ≡ w + 1 (mod k). Because both u and w are strictly positive and strictly less than k, neither is 0. Consequently, the modular wrap-around case (k - 1) + 1 ≡ 0 (mod k) cannot occur. Simplifying the modular arithmetic across all cases proves that w = u + 1 or u = w + 1.

    lines 12–33

    uses SimpleGraph.fromRel_adj, Nat.lt_or_ge, Nat.mod_eq_of_lt, Nat.mod_self

      have stepB : ∀ u w : Fin (k + m + l - 1), 0 < (u : ℕ) → (u : ℕ) < k → 0 < (w : ℕ) →
          (w : ℕ) < k → (simple_graph_kayak_paddle k m l).Adj u w →
          (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by
        intro u w hu huk hw hwk hadj
        simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj
        obtain ⟨-, h1 | h1⟩ := hadj
        · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1
          · rcases Nat.lt_or_ge ((u : ℕ) + 1) k with h2 | h2
            · rw [Nat.mod_eq_of_lt h2] at h1; omega
            · have : (u : ℕ) + 1 = k := by omega
              rw [this, Nat.mod_self] at h1; omega
          · omega
          · omega
          · omega
        · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1
          · rcases Nat.lt_or_ge ((w : ℕ) + 1) k with h2 | h2
            · rw [Nat.mod_eq_of_lt h2] at h1; omega
            · have : (w : ℕ) + 1 = k := by omega
              rw [this, Nat.mod_self] at h1; omega
          · omega
          · omega
          · omega
  3. Under the assumption that h(0) ≥ k, the inverse permutation g = h⁻¹ maps the open path T into itself and acts as a path neighbor: g(t) = t + 1 or t = g(t) + 1.

    Assume for contradiction that h(0) ≥ k. Setting g = h⁻¹, every vertex t is adjacent to g(t) because g(t) is adjacent to h(g(t)) = t. For any t in the open path T (0 < t < k), its neighbor g(t) must satisfy g(t) < k by stepA. Furthermore, g(t) cannot be 0, as g(t) = 0 would imply h(0) = h(g(t)) = t < k, contradicting h(0) ≥ k. Thus 0 < g(t) < k, meaning g(t) ∈ T. Applying stepB to the adjacent vertices t and g(t) in T shows that g(t) = t + 1 or t = g(t) + 1.

    lines 34–55

    uses not_lt, Fin.ext

      have hN : 0 < k + m + l - 1 := by omega
      have hjun : (h ⟨0, hN⟩ : ℕ) < k := by
        by_contra hlt
        rw [not_lt] at hlt
        obtain ⟨k2, hk2⟩ := he
        set g := h⁻¹ with hg
        have gT : ∀ t : Fin (k + m + l - 1), 0 < (t : ℕ) → (t : ℕ) < k →
            0 < (g t : ℕ) ∧ (g t : ℕ) < k ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by
          intro t ht htk
          have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by
            have := hh (g t)
            simpa [hg] using this
          have h1 : (g t : ℕ) < k := stepA (g t) t ht htk hadj.symm
          have h2 : (g t : ℕ) ≠ 0 := by
            intro heq
            have : g t = ⟨0, hN⟩ := Fin.ext heq
            have hgt : h (g t) = t := by simp [hg]
            rw [this] at hgt
            rw [hgt] at hlt
            omega
          have h3 : 0 < (g t : ℕ) := by omega
          exact ⟨h3, h1, (stepB (g t) t h3 h1 ht htk hadj).symm⟩
  4. The map ψ induced by g maps the odd vertices A ⊆ T into the even vertices B ⊆ T.

    Let A = {1 + 2t | 0 ≤ t < k/2} be the odd vertices in T and B = {2 + 2t | 0 ≤ t < k/2 - 1} be the even vertices in T. Since the affine maps t ↦ 1 + 2t and t ↦ 2 + 2t are injective, |A| = k/2 and |B| = k/2 - 1. For any a ∈ A, a is odd and in T, so g(a) ∈ T differs from a by 1. Being adjacent to an odd vertex along the path, g(a) must be an even vertex strictly between 0 and k, which places it in B.

    lines 56–76

    uses Finset.card_image_of_injective, Finset.card_range, Finset.mem_image, Finset.mem_range, dif_pos

        let ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0
        let A : Finset ℕ := (Finset.range (k / 2)).image (fun t => 1 + 2 * t)
        let B : Finset ℕ := (Finset.range (k / 2 - 1)).image (fun t => 2 + 2 * t)
        have hA : A.card = k / 2 :=
          by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range]
        have hB : B.card = k / 2 - 1 :=
          by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range]
        have hmaps : ∀ a ∈ A, ψ a ∈ B := by
          intro a ha
          simp only [A, Finset.mem_image, Finset.mem_range] at ha
          obtain ⟨t, ht, rfl⟩ := ha
          have hlt' : 1 + 2 * t < k + m + l - 1 := by omega
          have hgt := gT ⟨1 + 2 * t, hlt'⟩ (by show 0 < 1 + 2 * t; omega)
            (by show 1 + 2 * t < k; omega)
          simp only at hgt
          simp only [ψ, B, Finset.mem_image, Finset.mem_range]
          rw [dif_pos hlt']
          generalize hx : ((g ⟨1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt ⊢
          rcases hgt with ⟨h1, h1', h2 | h2⟩
          · exact ⟨t, by omega, by omega⟩
          · exact ⟨t - 1, by omega, by omega⟩
  5. The map ψ is injective on A, which forces |A| ≤ |B| and yields a contradiction, proving h(0) < k.

    Since g is a permutation, it is injective, so ψ is injective on A. By the pigeonhole principle (Finset.card_le_card_of_injOn), this injection implies |A| ≤ |B|, which means k/2 ≤ k/2 - 1. Linear arithmetic flags this contradiction, refuting the assumption h(0) ≥ k and concluding that h(0) < k.

    lines 77–90

    uses Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_range, dif_pos, Fin.ext, congrArg, Fin.val, Finset.card_le_card_of_injOn

        have hinj : Set.InjOn ψ A := by
          intro a ha b hb hab
          simp only [A, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_range] at ha hb
          obtain ⟨t, ht, rfl⟩ := ha
          obtain ⟨u, hu, rfl⟩ := hb
          have h1 : 1 + 2 * t < k + m + l - 1 := by omega
          have h2 : 1 + 2 * u < k + m + l - 1 := by omega
          simp only [ψ] at hab
          rw [dif_pos h1, dif_pos h2] at hab
          have := g.injective (Fin.ext hab)
          simpa using congrArg Fin.val this
        have := Finset.card_le_card_of_injOn ψ hmaps hinj
        rw [hA, hB] at this
        omega
  6. For every vertex v with v < k, h(v) < k.

    We split into cases on whether v = 0 or v > 0. If v = 0, h(v) < k is the junction result h(0) < k just established. If v > 0, then 0 < v < k, so v belongs to the open path T. Since h is a hop, h(v) is adjacent to v, so stepA immediately gives h(v) < k.

    lines 91–94

    uses Nat.eq_zero_or_pos, Fin.ext

      rcases Nat.eq_zero_or_pos (v : ℕ) with hv' | hv'
      · have : v = ⟨0, hN⟩ := Fin.ext hv'
        rw [this]; exact hjun
      · exact stepA (h v) v hv' hv (hh v)
SimpleGraph.fromRel_adj
In a graph defined from a relation r, two vertices v and w are adjacent if and only if v ≠ w and either r(v, w) or r(w, v) holds.
Nat.lt_or_ge
For any natural numbers n and m, either n < m or n ≥ m.
Nat.mod_eq_of_lt
If a natural number a is strictly less than b, then a % b = a.
Nat.mod_self
For any natural number n, n % n = 0.
not_lt
In a linear order, a is not strictly less than b if and only if b ≤ a.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the original set.
Finset.card_range
The finite set range n = {0, 1, ..., n - 1} has cardinality n.
Finset.mem_image
An element b belongs to the image of a finite set s under f if and only if b = f a for some a ∈ s.
Finset.mem_range
A natural number m belongs to range n if and only if m < n.
dif_pos
When a decidable condition c holds, the dependent conditional if c then t else e reduces to the then-branch.
Finset.coe_image
Coercing the image of a finite set to a set yields the set-theoretic image of the coerced set.
Set.mem_image
An element y belongs to the set image f '' s if and only if y = f x for some x ∈ s.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
congrArg
If two values are equal, then applying any function f to both yields equal results.
Fin.val
The canonical embedding mapping an element of Fin n to its underlying natural number.
Finset.card_le_card_of_injOn
If a function maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
Nat.eq_zero_or_pos
Every natural number is either equal to 0 or strictly positive.

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 kayak_paddle_hop_maps_first_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l)    (he : Even k) (h : Equiv.Perm (Fin (k + m + l - 1)))    (hh : simple_graph_is_hop (simple_graph_kayak_paddle k m l) h) (v : Fin (k + m + l - 1))    (hv : (v : ℕ) < k) : (h v : ℕ) < k := by  -- neighbours of the open path T = {v | 0 < v < k} stay in the first cycle  have stepA : ∀ u w : Fin (k + m + l - 1), 0 < (w : ℕ) → (w : ℕ) < k →      (simple_graph_kayak_paddle k m l).Adj w u → (u : ℕ) < k := by    intro u w hw hwk hadj    simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj    omega  -- adjacency inside T is adjacency along the path  have stepB : ∀ u w : Fin (k + m + l - 1), 0 < (u : ℕ) → (u : ℕ) < k → 0 < (w : ℕ) →      (w : ℕ) < k → (simple_graph_kayak_paddle k m l).Adj u w →      (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by    intro u w hu huk hw hwk hadj    simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj    obtain ⟨-, h1 | h1⟩ := hadj    · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1      · rcases Nat.lt_or_ge ((u : ℕ) + 1) k with h2 | h2        · rw [Nat.mod_eq_of_lt h2] at h1; omega        · have : (u : ℕ) + 1 = k := by omega          rw [this, Nat.mod_self] at h1; omega      · omega      · omega      · omega    · rcases h1 with ⟨-, -, h1⟩ | h1 | h1 | h1      · rcases Nat.lt_or_ge ((w : ℕ) + 1) k with h2 | h2        · rw [Nat.mod_eq_of_lt h2] at h1; omega        · have : (w : ℕ) + 1 = k := by omega          rw [this, Nat.mod_self] at h1; omega      · omega      · omega      · omega  have hN : 0 < k + m + l - 1 := by omega  have hjun : (h ⟨0, hN⟩ : ℕ) < k := by    by_contra hlt    rw [not_lt] at hlt    obtain ⟨k2, hk2⟩ := he    set g := h⁻¹ with hg    have gT : ∀ t : Fin (k + m + l - 1), 0 < (t : ℕ) → (t : ℕ) < k →        0 < (g t : ℕ) ∧ (g t : ℕ) < k ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by      intro t ht htk      have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by        have := hh (g t)        simpa [hg] using this      have h1 : (g t : ℕ) < k := stepA (g t) t ht htk hadj.symm      have h2 : (g t : ℕ) ≠ 0 := by        intro heq        have : g t = ⟨0, hN⟩ := Fin.ext heq        have hgt : h (g t) = t := by simp [hg]        rw [this] at hgt        rw [hgt] at hlt        omega      have h3 : 0 < (g t : ℕ) := by omega      exact ⟨h3, h1, (stepB (g t) t h3 h1 ht htk hadj).symm⟩    let ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0    let A : Finset ℕ := (Finset.range (k / 2)).image (fun t => 1 + 2 * t)    let B : Finset ℕ := (Finset.range (k / 2 - 1)).image (fun t => 2 + 2 * t)    have hA : A.card = k / 2 :=      by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range]    have hB : B.card = k / 2 - 1 :=      by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range]    have hmaps : ∀ a ∈ A, ψ a ∈ B := by      intro a ha      simp only [A, Finset.mem_image, Finset.mem_range] at ha      obtain ⟨t, ht, rfl⟩ := ha      have hlt' : 1 + 2 * t < k + m + l - 1 := by omega      have hgt := gT ⟨1 + 2 * t, hlt'⟩ (by show 0 < 1 + 2 * t; omega)        (by show 1 + 2 * t < k; omega)      simp only at hgt      simp only [ψ, B, Finset.mem_image, Finset.mem_range]      rw [dif_pos hlt']      generalize hx : ((g ⟨1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt ⊢      rcases hgt with ⟨h1, h1', h2 | h2⟩      · exact ⟨t, by omega, by omega⟩      · exact ⟨t - 1, by omega, by omega⟩    have hinj : Set.InjOn ψ A := by      intro a ha b hb hab      simp only [A, Finset.coe_image, Set.mem_image, Finset.mem_coe, Finset.mem_range] at ha hb      obtain ⟨t, ht, rfl⟩ := ha      obtain ⟨u, hu, rfl⟩ := hb      have h1 : 1 + 2 * t < k + m + l - 1 := by omega      have h2 : 1 + 2 * u < k + m + l - 1 := by omega      simp only [ψ] at hab      rw [dif_pos h1, dif_pos h2] at hab      have := g.injective (Fin.ext hab)      simpa using congrArg Fin.val this    have := Finset.card_le_card_of_injOn ψ hmaps hinj    rw [hA, hB] at this    omega  rcases Nat.eq_zero_or_pos (v : ℕ) with hv' | hv'  · have : v = ⟨0, hN⟩ := Fin.ext hv'    rw [this]; exact hjun  · exact stepA (h v) v hv' hv (hh v)
See it in the graphDiscuss this resultChallenge it