simple_graph_exists_geodesic_vertex_family
A shortest walk realises a geodesic: if x and y are reachable in G and dist x y = d, then there is a family of vertices (v_i)_{i ≤ d} with v_0 = x, v_d = y and dist (v i) (v j) = |i − j| (i.e. Nat.dist i j) for all i, j ≤ d.
Statement
theorem simple_graph_exists_geodesic_vertex_family {V : Type*} (G : SimpleGraph V) {x y : V} {d : ℕ} (hd : G.dist x y = d) (hr : G.Reachable x y) : ∃ v : ℕ → V, v 0 = x ∧ v d = y ∧ ∀ i j : ℕ, i ≤ d → j ≤ d → G.dist (v i) (v j) = Nat.dist i j
- Source
- step towards amply_regular_diameter_bound_qpk
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- Arena.Reachable.transReachability is transitive.
- Used by 2
- not_simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_boundThe statement
simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_boundis false: The statement is false due to truncated… - simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_bound_of_leDiscrete Bonnet–Myers: if every vertex of a finite graph G has degree k, c ≤ k, and every pair at distance 2 satisfies the one-sided…
- not_simple_graph_diam_le_two_mul_div_add_one_of_dist_two_transport_boundThe statement
The proof, explained
Because x and y are reachable and have distance d, there exists a shortest path p from x to y of length d. The vertex family is defined by taking v(i) to be the i-th vertex along p, which immediately matches the endpoints v(0) = x and v(d) = y. Any subsegment of a shortest walk is itself a shortest walk between its endpoints, so the distance between v(a) and v(b) for a ≤ b ≤ d equals the subsegment length b - a. The general pairwise distance dist(v(i), v(j)) = |i - j| follows for all i, j ≤ d by case analysis on the order of i and j using the symmetry of distance.
There exists a path p from x to y of length d realizing the graph distance between x and y.
Using classical logic, the reachability of y from x guarantees the existence of a path p whose length is the graph distance dist(x, y). Since dist(x, y) = d, the length of p is d.
classical obtain ⟨p, -, hp⟩ := hr.exists_path_of_dist have hlen : p.length = d := hp.trans hd
The family v(i) = p.getVert(i) satisfies the boundary conditions v(0) = x and v(d) = y.
We choose v to be the sequence of vertices along p, setting v(i) = p.getVert(i). The initial vertex is p.getVert(0) = x. Since p has length d, the d-th vertex is the terminal vertex p.getVert(p.length) = y.
refine ⟨fun i => p.getVert i, p.getVert_zero, ?_, ?_⟩ · rw [← hlen]; exact p.getVert_length
It suffices to show dist(v(i), v(j)) = Nat.dist i j for arbitrary indices i, j ≤ d.
We introduce arbitrary indices i, j ∈ ℕ along with the bounds i ≤ d and j ≤ d.
· intro i j hi hjFor any indices a ≤ b ≤ d, the distance between p.getVert(a) and p.getVert(b) equals b - a = Nat.dist a b.
Given a ≤ b ≤ d, consider the subwalk of p obtained by dropping the first a steps and then taking b - a steps. This is a subwalk of p by SimpleGraph.Walk.isSubwalk_take and SimpleGraph.Walk.isSubwalk_drop. Because p is a shortest path, SimpleGraph.length_eq_dist_of_subwalk implies that this subwalk is also a shortest walk between its endpoints. By SimpleGraph.Walk.take_length and SimpleGraph.Walk.drop_length, its length is min(b - a, d - a), which equals b - a by linear arithmetic since b ≤ d. Furthermore, by SimpleGraph.Walk.drop_getVert, the terminal vertex of this subwalk is p.getVert(a + (b - a)) = p.getVert(b). Hence the graph distance between p.getVert(a) and p.getVert(b) is b - a, which equals Nat.dist a b by Nat.dist_eq_sub_of_le.
uses
SimpleGraph.Walk.isSubwalk_take,SimpleGraph.Walk.isSubwalk_drop,SimpleGraph.length_eq_dist_of_subwalk,SimpleGraph.Walk.take_length,SimpleGraph.Walk.drop_length,SimpleGraph.Walk.drop_getVert,Nat.dist_eq_sub_of_lehave hmain : ∀ a b : ℕ, a ≤ b → b ≤ d → G.dist (p.getVert a) (p.getVert b) = Nat.dist a b := by intro a b hab hb have hsub : ((p.drop a).take (b - a)).IsSubwalk p := (SimpleGraph.Walk.isSubwalk_take _ _).trans (SimpleGraph.Walk.isSubwalk_drop _ _) have hq := SimpleGraph.length_eq_dist_of_subwalk hp hsub have htake : ((p.drop a).take (b - a)).length = b - a := by rw [SimpleGraph.Walk.take_length, SimpleGraph.Walk.drop_length, hlen] omega have hdist' : G.dist (p.getVert a) ((p.drop a).getVert (b - a)) = b - a := by rw [← hq, htake] have hget : (p.drop a).getVert (b - a) = p.getVert b := by rw [SimpleGraph.Walk.drop_getVert] congr 1 omega have h2 : G.dist (p.getVert a) (p.getVert b) = b - a := hget ▸ hdist' rw [h2, Nat.dist_eq_sub_of_le hab]
For all i, j ≤ d, the distance between v(i) and v(j) equals Nat.dist i j.
By the totality of the linear order on ℕ (le_total), either i ≤ j or j ≤ i. If i ≤ j, the result follows immediately from the subwalk distance formula. If j ≤ i, the formula gives dist(v(j), v(i)) = Nat.dist j i, and the claim follows by the symmetry of graph distance (SimpleGraph.dist_comm) and of distance in ℕ (Nat.dist_comm).
uses
le_total,SimpleGraph.dist_comm,Nat.dist_commrcases le_total i j with h | h · exact hmain i j h hj · rw [SimpleGraph.dist_comm, Nat.dist_comm] exact hmain j i h hi
SimpleGraph.Walk.isSubwalk_take- Taking the prefix of length n of a walk p produces a subwalk of p.
SimpleGraph.Walk.isSubwalk_drop- Dropping the first n steps of a walk p produces a subwalk of p.
SimpleGraph.length_eq_dist_of_subwalk- Any subwalk of a walk that realizes the graph distance between its endpoints also realizes the graph distance between its own endpoints.
SimpleGraph.Walk.take_length- The length of the prefix of length n of a walk p is min(n, p.length).
SimpleGraph.Walk.drop_length- The length of the walk obtained by dropping the first n steps from p is p.length - n.
SimpleGraph.Walk.drop_getVert- The m-th vertex of (p.drop n) is the (n + m)-th vertex of p.
Nat.dist_eq_sub_of_le- For natural numbers n ≤ m, the distance |n - m| equals m - n.
le_total- In a linear order, any two elements a and b satisfy a ≤ b or b ≤ a.
SimpleGraph.dist_comm- Graph distance is symmetric: dist(u, v) = dist(v, u).
Nat.dist_comm- Distance between natural numbers is symmetric: |n - m| = |m - n|.
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.
/-- A shortest walk yields a geodesic family of vertices indexed by 0, …, dist x y, whose pairwise distances are the index distances. -/theorem simple_graph_exists_geodesic_vertex_family {V : Type*} (G : SimpleGraph V) {x y : V} {d : ℕ} (hd : G.dist x y = d) (hr : G.Reachable x y) : ∃ v : ℕ → V, v 0 = x ∧ v d = y ∧ ∀ i j : ℕ, i ≤ d → j ≤ d → G.dist (v i) (v j) = Nat.dist i j := by classical obtain ⟨p, -, hp⟩ := hr.exists_path_of_dist have hlen : p.length = d := hp.trans hd refine ⟨fun i => p.getVert i, p.getVert_zero, ?_, ?_⟩ · rw [← hlen]; exact p.getVert_length · intro i j hi hj have hmain : ∀ a b : ℕ, a ≤ b → b ≤ d → G.dist (p.getVert a) (p.getVert b) = Nat.dist a b := by intro a b hab hb have hsub : ((p.drop a).take (b - a)).IsSubwalk p := (SimpleGraph.Walk.isSubwalk_take _ _).trans (SimpleGraph.Walk.isSubwalk_drop _ _) have hq := SimpleGraph.length_eq_dist_of_subwalk hp hsub have htake : ((p.drop a).take (b - a)).length = b - a := by rw [SimpleGraph.Walk.take_length, SimpleGraph.Walk.drop_length, hlen] omega have hdist' : G.dist (p.getVert a) ((p.drop a).getVert (b - a)) = b - a := by rw [← hq, htake] have hget : (p.drop a).getVert (b - a) = p.getVert b := by rw [SimpleGraph.Walk.drop_getVert] congr 1 omega have h2 : G.dist (p.getVert a) (p.getVert b) = b - a := hget ▸ hdist' rw [h2, Nat.dist_eq_sub_of_le hab] rcases le_total i j with h | h · exact hmain i j h hj · rw [SimpleGraph.dist_comm, Nat.dist_comm] exact hmain j i h hi