AFTD Auto-Formalizing Theoretical Domains

simple_graph_path_graph_walk_length_ge

theoremverified

Every walk in the path graph P_n from u to v has length at least |u - v|.

Statement

theorem simple_graph_path_graph_walk_length_ge {n : ℕ} {u v : Fin n}
    (p : (SimpleGraph.pathGraph n).Walk u v) : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| ≤ p.length
Source
for simple_graph_path_radio_labeling_four_mul_add_three (RT-4, OP-384)
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

The proof, explained

The theorem is proved by induction on the walk p. The base case of an empty walk is immediate because both the distance between identical vertices and the walk length are zero. For the inductive step, extending a walk p from b to c by an edge a ~ b increases the length by 1, and adjacency in the path graph means a and b differ by 1. The target bound |a - c| ≤ length(p) + 1 is then proved by case analysis on the signs of a - c and b - c, with each case solved by linear integer arithmetic combining the edge difference and the induction hypothesis.

  1. The inequality holds for the empty walk (the base case).

    We induct on the walk p. In the base case, p is the empty walk from a vertex to itself. Its length is 0, and the distance between identical vertices is |u - u| = 0, so the inequality 0 ≤ 0 holds immediately by simplification.

    lines 3–4

      induction p with
      | nil => simp
  2. In the inductive step, the walk length is expressed as length(p) + 1, and the adjacency of the initial edge is translated into integer arithmetic.

    For the inductive step, the walk begins with an edge between vertices a and b, followed by a walk p from b to c, with induction hypothesis |b - c| ≤ length(p). In the path graph, adjacency of a and b means a + 1 = b ∨ b + 1 = a by SimpleGraph.pathGraph_adj. Rewriting with SimpleGraph.Walk.length_cons, Nat.cast_add, and Nat.cast_one establishes that the extended walk has length length(p) + 1 in the integers. The adjacency relation is then cast from ℕ to ℤ, giving a + 1 = b ∨ b + 1 = a as an integer statement.

    lines 5–9

    uses SimpleGraph.pathGraph_adj, SimpleGraph.Walk.length_cons, Nat.cast_add, Nat.cast_one

      | cons h p ih =>
        rename_i a b c
        rw [SimpleGraph.pathGraph_adj] at h
        simp only [SimpleGraph.Walk.length_cons, Nat.cast_add, Nat.cast_one]
        have h' : ((a : ℕ) : ℤ) + 1 = ((b : ℕ) : ℤ) ∨ ((b : ℕ) : ℤ) + 1 = ((a : ℕ) : ℤ) := by omega
  3. Case analysis on the signs of a - c and b - c completes the inductive step.

    Using abs_cases, we split into cases depending on the signs of a - c and b - c. In each of the resulting four subgoals, the absolute values |a - c| and |b - c| unfold to either the difference or its negation. Substituting these into the goal and the induction hypothesis reduces the problem to linear integer inequalities, which are then solved alongside the adjacency relation a + 1 = b ∨ b + 1 = a by linear integer arithmetic (omega).

    lines 10–12

    uses abs_cases

        rcases abs_cases (((a : ℕ) : ℤ) - ((c : ℕ) : ℤ)) with ⟨h1, _⟩ | ⟨h1, _⟩ <;>
        rcases abs_cases (((b : ℕ) : ℤ) - ((c : ℕ) : ℤ)) with ⟨h2, _⟩ | ⟨h2, _⟩ <;>
        · rw [h1]; rw [h2] at ih; omega
SimpleGraph.pathGraph_adj
Two vertices in the path graph P_n are adjacent if and only if their natural-number indices differ by 1 (u + 1 = v or v + 1 = u).
SimpleGraph.Walk.length_cons
The length of a walk formed by prepending an edge u ~ v to a walk from v to w is the length of the tail walk plus 1.
Nat.cast_add
The canonical cast from ℕ to an additive monoid with one preserves addition: ↑(m + n) = ↑m + ↑n.
Nat.cast_one
The canonical cast of the natural number 1 to an additive monoid with one is 1.
abs_cases
For any element a in a linearly ordered additive group, either |a| = a with 0 ≤ a, or |a| = -a with a < 0.

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_path_graph_walk_length_ge {n : ℕ} {u v : Fin n}    (p : (SimpleGraph.pathGraph n).Walk u v) : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| ≤ p.length := by  induction p with  | nil => simp  | cons h p ih =>    rename_i a b c    rw [SimpleGraph.pathGraph_adj] at h    simp only [SimpleGraph.Walk.length_cons, Nat.cast_add, Nat.cast_one]    have h' : ((a : ℕ) : ℤ) + 1 = ((b : ℕ) : ℤ) ∨ ((b : ℕ) : ℤ) + 1 = ((a : ℕ) : ℤ) := by omega    rcases abs_cases (((a : ℕ) : ℤ) - ((c : ℕ) : ℤ)) with ⟨h1, _⟩ | ⟨h1, _⟩ <;>    rcases abs_cases (((b : ℕ) : ℤ) - ((c : ℕ) : ℤ)) with ⟨h2, _⟩ | ⟨h2, _⟩ <;>    · rw [h1]; rw [h2] at ih; omega
See it in the graphDiscuss this resultChallenge it