distance_regular_exists_dist_eq_succ
In any finite distance-regular graph G with parameters d, b, c, for every index i : Fin d, there exist vertices u, v at distance i + 1.
Statement
theorem distance_regular_exists_dist_eq_succ {V : Type*} [Fintype V] (G : SimpleGraph V) (d : ℕ) (b c : Fin d → ℕ) (hG : is_distance_regular_with G d b c) (i : Fin d) : ∃ u v : V, G.dist u v = i.val + 1
- Source
- step towards op_1146_classification_realizable_intersection_array_k_geodetic
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- is_distance_regular_withA simple graph G on vertex type V is a distance-regular graph with diameter d : ℕ and intersection parameters b, c : Fin d → ℕ if: G is…
The proof, explained
Since G is a finite connected distance-regular graph of diameter d, there exist vertices u and v at maximum distance d, joined by a geodesic walk p of length d. For any index i ∈ {0, …, d - 1}, the value i + 1 is at most d, so we can consider the vertex reached after i + 1 steps along p. Because every subwalk of a geodesic is itself a geodesic between its endpoints, the initial segment of p of length i + 1 proves that the distance from u to this vertex is exactly i + 1.
G is a connected graph of diameter d, and its vertex set V is nonempty.
From the definition of distance-regularity hG, we unpack that G is connected and has diameter d. Since G is connected, its vertex set V is nonempty.
obtain ⟨conn, hdiam, hb, hc⟩ := hG haveI hne : Nonempty V := conn.nonemptyThere exist vertices u, v at distance d, connected by a walk p of length d.
In any finite nonempty graph, the diameter is attained by some pair of vertices u, v, so dist(u, v) = d. Because G is connected, there exists a walk p from u to v whose length equals dist(u, v) = d, which is a geodesic between u and v.
obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam rw [hdiam] at huv obtain ⟨p, hp⟩ := conn.exists_walk_length_eq_dist u v
i + 1 ≤ length(p).
Since i is an element of Fin d, we have i < d, so i + 1 ≤ d by Nat.succ_le_of_lt. Rewriting with length(p) = dist(u, v) = d yields i + 1 ≤ length(p).
uses
Nat.succ_le_of_lthave hle : i.val + 1 ≤ p.length := by rw [hp, huv]; exact Nat.succ_le_of_lt i.isLt
It suffices to show that dist(u, p.getVert(i + 1)) = i + 1.
We choose u and the vertex reached after i + 1 steps along the geodesic p as the witnesses, reducing the goal to showing that their graph distance is i + 1.
refine ⟨u, p.getVert (i.val + 1), ?_⟩The prefix walk of p of length i + 1 is a subwalk of p of length exactly i + 1.
Taking the first i + 1 steps of p yields a subwalk of p. By SimpleGraph.Walk.take_length, the length of this prefix is min(i + 1, length(p)), which equals i + 1 by min_eq_left since i + 1 ≤ length(p).
uses
SimpleGraph.Walk.take_length,min_eq_lefthave hsub := p.isSubwalk_take (i.val + 1) have hlen : (p.take (i.val + 1)).length = i.val + 1 := by rw [SimpleGraph.Walk.take_length, min_eq_left hle]
dist(u, p.getVert(i + 1)) = i + 1.
By SimpleGraph.length_eq_dist_of_subwalk, any subwalk of a geodesic is itself a geodesic between its own endpoints. Therefore, the distance between u and the (i + 1)-th vertex along p equals the length of the prefix walk, which is i + 1.
uses
SimpleGraph.length_eq_dist_of_subwalkhave hdist := SimpleGraph.length_eq_dist_of_subwalk hp hsub rw [← hdist, hlen]
Nat.succ_le_of_lt- If n < m for natural numbers n and m, then n + 1 ≤ m.
SimpleGraph.Walk.take_length- The length of the prefix of a walk p truncated to at most n steps is min(n, length(p)).
min_eq_left- If a ≤ b in a linear order, then min(a, b) = a.
SimpleGraph.length_eq_dist_of_subwalk- If a walk has length equal to the distance between its endpoints (a geodesic), then any subwalk also has length equal to the distance between the subwalk's endpoints.
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.
/-- In any finite distance-regular graph with diameter d and parameters b, c, every distance 1 ≤ i + 1 ≤ d is attained by some pair of vertices. -/theorem distance_regular_exists_dist_eq_succ {V : Type*} [Fintype V] (G : SimpleGraph V) (d : ℕ) (b c : Fin d → ℕ) (hG : is_distance_regular_with G d b c) (i : Fin d) : ∃ u v : V, G.dist u v = i.val + 1 := by obtain ⟨conn, hdiam, hb, hc⟩ := hG haveI hne : Nonempty V := conn.nonempty obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam rw [hdiam] at huv obtain ⟨p, hp⟩ := conn.exists_walk_length_eq_dist u v have hle : i.val + 1 ≤ p.length := by rw [hp, huv]; exact Nat.succ_le_of_lt i.isLt refine ⟨u, p.getVert (i.val + 1), ?_⟩ have hsub := p.isSubwalk_take (i.val + 1) have hlen : (p.take (i.val + 1)).length = i.val + 1 := by rw [SimpleGraph.Walk.take_length, min_eq_left hle] have hdist := SimpleGraph.length_eq_dist_of_subwalk hp hsub rw [← hdist, hlen]