simple_graph_path_graph_dist_ge
In the path graph P_n the distance between u and v is at least |u - v|.
Statement
theorem simple_graph_path_graph_dist_ge {n : ℕ} (u v : Fin n) :
|((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| ≤ (SimpleGraph.pathGraph n).dist u v- 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 1
- simple_graph_path_graph_walk_length_geEvery walk in the path graph P_n from u to v has length at least |u - v|.
- Used by 3
- simple_graph_path_radio_labeling_four_mul_add_threeFor m >= 1, the labeling of the path P_{4m+3} that gives an odd vertex v the labels v, v+4, ..., v+4(m-1) and an even vertex v the labels…
- simple_graph_multi_radio_number_path_le_eight_mulFor n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.
- path_three_radio_labeling_span_ge_sevenFor n >= 8, every (1,3)-radio labeling of the path P_n has span at least 7; combined with the upper bound 8m-1 at m = 1 this gives that…
The proof, explained
The proof relies on the preconnectedness of the path graph P_n, which guarantees that between any two vertices u and v there exists a walk whose length equals the graph distance dist(u, v). The distance bound then follows directly from the previously established lemma showing that every walk between u and v in P_n has length at least |u - v|.
There exists a walk p from u to v whose length equals the graph distance between u and v.
Because the path graph on n vertices is preconnected (SimpleGraph.pathGraph_preconnected), u can reach v. Therefore, exists_walk_length_eq_dist provides a walk p from u to v whose length equals the distance dist(u, v).
uses
SimpleGraph.pathGraph_preconnected,exists_walk_length_eq_distobtain ⟨p, hp⟩ := (SimpleGraph.pathGraph_preconnected n u v).exists_walk_length_eq_distThe distance between u and v is at least |u - v|.
Rewriting the distance in the goal with the length of p using the equality p.length = dist(u, v), it suffices to show |u - v| ≤ p.length. This holds directly by simple_graph_path_graph_walk_length_ge, which bounds the length of any walk in P_n between u and v from below by |u - v|.
uses
simple_graph_path_graph_walk_length_gerw [← hp] exact simple_graph_path_graph_walk_length_ge p
SimpleGraph.pathGraph_preconnected- For every natural number n, the path graph on n vertices is preconnected, meaning any two vertices can reach each other.
exists_walk_length_eq_dist- If two vertices in a graph are reachable from each other, there exists a walk between them whose length equals the graph distance between them.
simple_graph_path_graph_walk_length_ge- In the path graph on n vertices, every walk between vertices u and v has length at least |u - v|.
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_dist_ge {n : ℕ} (u v : Fin n) : |((u : ℕ) : ℤ) - ((v : ℕ) : ℤ)| ≤ (SimpleGraph.pathGraph n).dist u v := by obtain ⟨p, hp⟩ := (SimpleGraph.pathGraph_preconnected n u v).exists_walk_length_eq_dist rw [← hp] exact simple_graph_path_graph_walk_length_ge p