simple_graph_path_graph_walk_length_ge
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
- Used by 1
- simple_graph_path_graph_dist_geIn the path graph P_n the distance between u and v is at least |u - v|.
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.
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.
induction p with | nil => simp
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.
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 omegaCase 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).
uses
abs_casesrcases 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.
- On paper, the inductive step is a direct application of the triangle inequality |a - c| ≤ |a - b| + |b - c| ≤ 1 + length(p). In the Lean proof, this is instead verified by case analysis on the signs of a - c and b - c via `abs_cases`, delegating each of the four cases to linear integer arithmetic (`omega`).
- Line 9 explicitly casts the adjacency condition a + 1 = b ∨ b + 1 = a from ℕ to ℤ as an auxiliary hypothesis h' so that `omega` can use it in integer arithmetic.
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_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