AFTD Auto-Formalizing Theoretical Domains

distance_regular_exists_dist_eq_succ

theoremverified

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.

  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.

    lines 6–7

      obtain ⟨conn, hdiam, hb, hc⟩ := hG
      haveI hne : Nonempty V := conn.nonempty
  2. There 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.

    lines 8–10

      obtain ⟨u, v, huv⟩ := G.exists_dist_eq_diam
      rw [hdiam] at huv
      obtain ⟨p, hp⟩ := conn.exists_walk_length_eq_dist u v
  3. 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).

    lines 11–12

    uses Nat.succ_le_of_lt

      have hle : i.val + 1 ≤ p.length := by
        rw [hp, huv]; exact Nat.succ_le_of_lt i.isLt
  4. 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.

    line 13

      refine ⟨u, p.getVert (i.val + 1), ?_⟩
  5. 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).

    lines 14–16

    uses SimpleGraph.Walk.take_length, min_eq_left

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

    lines 17–18

    uses SimpleGraph.length_eq_dist_of_subwalk

      have 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

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