AFTD Auto-Formalizing Theoretical Domains

kayak_paddle_hop_maps_second_cycle

theoremverified

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

Statement

theorem kayak_paddle_hop_maps_second_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l)
    (he : Even m) (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 : k + l - 1 ≤ (v : ℕ)) : k + l - 1 ≤ (h v : ℕ)
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 vertex set of the second cycle C_m in the kayak paddle graph KP(k, m, l) consists of all vertices with index at least the junction s = k + l - 1. The proof shows that any hop h preserves this set by first showing that neighbours of the open path T = {v | s < v} cannot leave the second cycle, and that adjacency inside T is simply path adjacency. It then proves that the junction vertex s cannot be mapped out of the second cycle: if h s < s, the inverse hop g = h⁻¹ would map T into itself by shifting each vertex by ±1, which would injectively map the m/2 vertices with odd offset from s into the m/2 - 1 vertices with even offset, violating the pigeonhole principle since m is even. Finally, combining the junction property with the path neighbour property ensures every vertex with s ≤ v satisfies s ≤ h v.

  1. Any neighbour of a vertex in the open path T = {w | s < w} belongs to the second cycle (has index at least s).

    We define the junction vertex s = k + l - 1, which connects the handle path to the second cycle C_m. Any vertex w with s < w lies strictly inside C_m. Unfolding the definition of adjacency in the kayak paddle graph (simple_graph_kayak_paddle, SimpleGraph.fromRel_adj), the only edges incident to w are within C_m, connecting to vertices with index at least s. Linear arithmetic (omega) verifies that no edges to the handle or the first cycle can reach w.

    lines 5–11

    uses simple_graph_kayak_paddle, SimpleGraph.fromRel_adj

      set s := k + l - 1 with hs
      -- neighbours of the open path T = {v | s < v} stay in the second cycle
      have stepA : ∀ u w : Fin (k + m + l - 1), s < (w : ℕ) →
          (simple_graph_kayak_paddle k m l).Adj w u → s ≤ (u : ℕ) := by
        intro u w hw hadj
        simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj
        omega
  2. Any two adjacent vertices in the open path T are consecutive along the path (w = u + 1 or u = w + 1).

    Suppose u and w both lie strictly beyond s and are adjacent. From the kayak paddle relation, the only possible adjacency between them is within C_m, where their offsets from s satisfy (w - s) = (u - s + 1) % m (or symmetrically). By splitting on whether (u - s + 1) < m or ≥ m (Nat.lt_or_ge): if it is less than m, the modulo is the identity (Nat.mod_eq_of_lt), so w = u + 1; if it is at least m, since u < k + m + l - 1, the offset equals m, making the modulo zero (Nat.mod_self), which would mean w = s, contradicting s < w. The symmetric case is identical.

    lines 13–35

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

      have stepB : ∀ u w : Fin (k + m + l - 1), s < (u : ℕ) → s < (w : ℕ) →
          (simple_graph_kayak_paddle k m l).Adj u w → (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by
        intro u w hu hw hadj
        have hu' := u.isLt
        have hw' := w.isLt
        simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj
        obtain ⟨-, h1 | h1⟩ := hadj
        · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩
          · omega
          · omega
          · omega
          · rcases Nat.lt_or_ge ((u : ℕ) - s + 1) m with h2 | h2
            · rw [Nat.mod_eq_of_lt h2] at h1; omega
            · have : (u : ℕ) - s + 1 = m := by omega
              rw [this, Nat.mod_self] at h1; omega
        · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩
          · omega
          · omega
          · omega
          · rcases Nat.lt_or_ge ((w : ℕ) - s + 1) m with h2 | h2
            · rw [Nat.mod_eq_of_lt h2] at h1; omega
            · have : (w : ℕ) - s + 1 = m := by omega
              rw [this, Nat.mod_self] at h1; omega
  3. Set up proof by contradiction that the junction vertex s remains in the second cycle, s ≤ h s.

    We note that s is strictly less than the total number of vertices (hN). To prove that h maps s into the second cycle (s ≤ h s), we suppose for contradiction that h s < s (by_contra, not_le), and unpack the hypothesis that m is even.

    lines 37–41

    uses not_le

      have hN : s < k + m + l - 1 := by omega
      have hjun : s ≤ (h ⟨s, hN⟩ : ℕ) := by
        by_contra hlt
        rw [not_le] at hlt
        obtain ⟨m2, hm2⟩ := he
  4. The inverse permutation g = h⁻¹ maps the open path T into itself, shifting each vertex by ±1 along the path.

    Since h is a hop, g t is adjacent to h (g t) = t. For any t in T (s < t), stepA implies s ≤ g t. If g t were s, then applying h would yield t = h s < s, contradicting s < t (Fin.ext). Hence s < g t, so g t is in T. Since both t and g t are in T and adjacent, stepB ensures that g t = t + 1 or t = g t + 1.

    lines 43–59

    uses Fin.ext

        set g := h⁻¹ with hg
        have gT : ∀ t : Fin (k + m + l - 1), s < (t : ℕ) →
            s < (g t : ℕ) ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by
          intro t ht
          have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by
            have := hh (g t)
            simpa [hg] using this
          have h1 : s ≤ (g t : ℕ) := stepA (g t) t ht hadj.symm
          have h2 : (g t : ℕ) ≠ s := by
            intro heq
            have : g t = ⟨s, hN⟩ := Fin.ext heq
            have hgt : h (g t) = t := by simp [hg]
            rw [this] at hgt
            rw [hgt] at hlt
            omega
          have h3 : s < (g t : ℕ) := by omega
          exact ⟨h3, (stepB (g t) t h3 ht hadj).symm⟩
  5. The assumption h s < s leads to a contradiction via a parity counting argument on T.

    We consider the action ψ of g on indices, restricted to the set A of odd offsets from s (size m / 2) and the set B of even offsets from s (size m / 2 - 1) (Finset.card_image_of_injective, Finset.card_range). Since g shifts each vertex by ±1, it flips parity, mapping elements of A into B (Finset.mem_image, Finset.mem_range, dif_pos, Fin.val_mk). Because g is a permutation, ψ is injective on A (Set.InjOn, Finset.coe_image, Set.mem_image, Finset.mem_coe, Fin.ext, congrArg, Fin.val). By the pigeonhole principle (Finset.card_le_card_of_injOn), |A| ≤ |B|, meaning m / 2 ≤ m / 2 - 1, which is impossible (omega). Thus s ≤ h s.

    lines 61–95

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

        let ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0
        let A : Finset ℕ := (Finset.range (m / 2)).image (fun t => s + 1 + 2 * t)
        let B : Finset ℕ := (Finset.range (m / 2 - 1)).image (fun t => s + 2 + 2 * t)
        have hA : A.card = m / 2 :=
          by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range]
        have hB : B.card = m / 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' : s + 1 + 2 * t < k + m + l - 1 := by omega
          have hgt := gT ⟨s + 1 + 2 * t, hlt'⟩ (by show s < s + 1 + 2 * t; omega)
          simp only [Fin.val_mk] at hgt
          have hbound := (g ⟨s + 1 + 2 * t, hlt'⟩).isLt
          simp only [ψ, B, Finset.mem_image, Finset.mem_range]
          rw [dif_pos hlt']
          generalize hx : ((g ⟨s + 1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt hbound ⊢
          rcases hgt with ⟨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 : s + 1 + 2 * t < k + m + l - 1 := by omega
          have h2 : s + 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. Every vertex in the second cycle (s ≤ v) is mapped into the second cycle (s ≤ h v).

    We split into cases on whether v = s or s < v (Nat.eq_or_lt_of_le). If v = s, then h v = h s ≥ s by the junction property established above (Fin.ext). If s < v, then v lies in the open path T; since h v is adjacent to v by the hop hypothesis, stepA directly implies s ≤ h v.

    lines 97–100

    uses Nat.eq_or_lt_of_le, Fin.ext

      rcases Nat.eq_or_lt_of_le hv with hv' | hv'
      · have : v = ⟨s, hN⟩ := Fin.ext hv'.symm
        rw [this]; exact hjun
      · exact stepA (h v) v hv' (hh v)
simple_graph_kayak_paddle
definition of the kayak paddle graph KP(k, m, l), consisting of a k-cycle, a path of length l, and an m-cycle
SimpleGraph.fromRel_adj
two vertices in a graph built from a relation are adjacent if and only if they are distinct and related in either direction
Nat.lt_or_ge
for any natural numbers n and m, either n < m or n ≥ m
Nat.mod_eq_of_lt
if a < b, then a % b = a
Nat.mod_self
for any natural number n, n % n = 0
not_le
in a linear order, ¬(a ≤ b) is equivalent to b < a
Fin.ext
two elements of Fin n are equal if their underlying natural values are equal
Finset.card_image_of_injective
the image of a finite set under an injective map 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 is in the image of a finite set under f if and only if it is f(a) for some element a in the set
Finset.mem_range
a natural number m is in range n if and only if m < n
Fin.val_mk
the underlying natural value of ⟨m, h⟩ in Fin n is m
dif_pos
a dependent if-then-else expression evaluates to the then-branch when the condition is true
Finset.coe_image
the set coercion of the image of a finite set is the image of the set coercion
Set.mem_image
an element y is in f '' s if and only if y = f x for some x in s
Finset.mem_coe
an element is in the set coercion of a finite set if and only if it is in the finite set
congrArg
if two inputs are equal, then the values of a function applied to them are equal
Fin.val
the canonical projection from Fin n to ℕ giving its underlying value
Finset.card_le_card_of_injOn
an injective map from a finite set s into a finite set t implies |s| ≤ |t|
Nat.eq_or_lt_of_le
if n ≤ m, then n = m or n < m

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_second_cycle (k m l : ℕ) (hk : 3 ≤ k) (hm : 3 ≤ m) (hl : 1 ≤ l)    (he : Even m) (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 : k + l - 1 ≤ (v : ℕ)) : k + l - 1 ≤ (h v : ℕ) := by  set s := k + l - 1 with hs  -- neighbours of the open path T = {v | s < v} stay in the second cycle  have stepA : ∀ u w : Fin (k + m + l - 1), s < (w : ℕ) →      (simple_graph_kayak_paddle k m l).Adj w u → s ≤ (u : ℕ) := by    intro u w hw 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), s < (u : ℕ) → s < (w : ℕ) →      (simple_graph_kayak_paddle k m l).Adj u w → (w : ℕ) = u + 1 ∨ (u : ℕ) = w + 1 := by    intro u w hu hw hadj    have hu' := u.isLt    have hw' := w.isLt    simp only [simple_graph_kayak_paddle, SimpleGraph.fromRel_adj] at hadj    obtain ⟨-, h1 | h1⟩ := hadj    · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩      · omega      · omega      · omega      · rcases Nat.lt_or_ge ((u : ℕ) - s + 1) m with h2 | h2        · rw [Nat.mod_eq_of_lt h2] at h1; omega        · have : (u : ℕ) - s + 1 = m := by omega          rw [this, Nat.mod_self] at h1; omega    · rcases h1 with h1 | h1 | h1 | ⟨-, -, h1⟩      · omega      · omega      · omega      · rcases Nat.lt_or_ge ((w : ℕ) - s + 1) m with h2 | h2        · rw [Nat.mod_eq_of_lt h2] at h1; omega        · have : (w : ℕ) - s + 1 = m := by omega          rw [this, Nat.mod_self] at h1; omega  -- first: h s lies in the second cycle  have hN : s < k + m + l - 1 := by omega  have hjun : s ≤ (h ⟨s, hN⟩ : ℕ) := by    by_contra hlt    rw [not_le] at hlt    obtain ⟨m2, hm2⟩ := he    -- g = h⁻¹ maps T into T, moving each point by one along the path    set g := h⁻¹ with hg    have gT : ∀ t : Fin (k + m + l - 1), s < (t : ℕ) →        s < (g t : ℕ) ∧ ((g t : ℕ) = t + 1 ∨ (t : ℕ) = g t + 1) := by      intro t ht      have hadj : (simple_graph_kayak_paddle k m l).Adj (g t) t := by        have := hh (g t)        simpa [hg] using this      have h1 : s ≤ (g t : ℕ) := stepA (g t) t ht hadj.symm      have h2 : (g t : ℕ) ≠ s := by        intro heq        have : g t = ⟨s, hN⟩ := Fin.ext heq        have hgt : h (g t) = t := by simp [hg]        rw [this] at hgt        rw [hgt] at hlt        omega      have h3 : s < (g t : ℕ) := by omega      exact ⟨h3, (stepB (g t) t h3 ht hadj).symm⟩    -- counting: odd offsets map injectively to even offsets    let ψ : ℕ → ℕ := fun a => if ha : a < k + m + l - 1 then (g ⟨a, ha⟩ : ℕ) else 0    let A : Finset ℕ := (Finset.range (m / 2)).image (fun t => s + 1 + 2 * t)    let B : Finset ℕ := (Finset.range (m / 2 - 1)).image (fun t => s + 2 + 2 * t)    have hA : A.card = m / 2 :=      by rw [Finset.card_image_of_injective _ (fun x y hxy => by simp at hxy; omega), Finset.card_range]    have hB : B.card = m / 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' : s + 1 + 2 * t < k + m + l - 1 := by omega      have hgt := gT ⟨s + 1 + 2 * t, hlt'⟩ (by show s < s + 1 + 2 * t; omega)      simp only [Fin.val_mk] at hgt      have hbound := (g ⟨s + 1 + 2 * t, hlt'⟩).isLt      simp only [ψ, B, Finset.mem_image, Finset.mem_range]      rw [dif_pos hlt']      generalize hx : ((g ⟨s + 1 + 2 * t, hlt'⟩ : Fin _) : ℕ) = x at hgt hbound ⊢      rcases hgt with ⟨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 : s + 1 + 2 * t < k + m + l - 1 := by omega      have h2 : s + 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  -- then every vertex of the second cycle stays there  rcases Nat.eq_or_lt_of_le hv with hv' | hv'  · have : v = ⟨s, hN⟩ := Fin.ext hv'.symm    rw [this]; exact hjun  · exact stepA (h v) v hv' (hh v)
See it in the graphDiscuss this resultChallenge it