AFTD Auto-Formalizing Theoretical Domains

simple_graph_path_graph_dist_ge

theoremverified

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
Used by 3

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|.

  1. 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).

    line 3

    uses SimpleGraph.pathGraph_preconnected, exists_walk_length_eq_dist

      obtain ⟨p, hp⟩ := (SimpleGraph.pathGraph_preconnected n u v).exists_walk_length_eq_dist
  2. The 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|.

    lines 4–5

    uses simple_graph_path_graph_walk_length_ge

      rw [← 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

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
See it in the graphDiscuss this resultChallenge it