AFTD Auto-Formalizing Theoretical Domains

simple_graph_diam_le_of_forall_exists_walk_le

theoremverified

In any simple graph G on a type α, if for every pair of vertices u and v there exists a walk from u to v of length at most D, then the diameter of G is at most D.

Statement

theorem simple_graph_diam_le_of_forall_exists_walk_le
    {α : Type*} (G : SimpleGraph α) (D : ℕ)
    (h : ∀ u v : α, ∃ w : G.Walk u v, w.length ≤ D) :
    G.diam ≤ D
Source
Mathlib.Combinatorics.SimpleGraph.Diam
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For every type α, every simple graph G on α, and every natural number D, if for all vertices u and v in α there exists a walk w from u to v in G such that the length of w is at most D, then the diameter of G (G.diam) is at most D.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof reduces the diameter bound to bounding the pairwise extended distances in G: the diameter is at most D as long as every two vertices are at extended distance at most D. For any vertices u and v, the hypothesis provides a walk between them of length at most D. Since the distance between two vertices is bounded above by the length of any connecting walk, the extended distance is at most D, which completes the proof.

  1. It suffices to show that the extended distance between any two vertices in G is at most D.

    By `ENat.toNat_le_of_le_natCast`, bounding the diameter `G.diam` (which is `G.ediam.toNat`) by D reduces to showing that the extended diameter `G.ediam ≤ D`. Applying `G.ediam_le_iff` rewrites this into the condition that `G.edist u v ≤ D` for all pairs of vertices u and v.

    lines 6–7

    uses ENat.toNat_le_of_le_natCast, G.ediam_le_iff

      apply ENat.toNat_le_of_le_natCast
      rw [G.ediam_le_iff]
  2. For every pair of vertices u and v, the extended distance between them is at most D.

    Let u and v be arbitrary vertices in G. The hypothesis provides a walk w connecting u to v with length at most D. The extended distance between u and v is bounded above by the length of w, which is at most D by transitivity and monotonicity of casting (`Nat.cast_le.mpr`).

    lines 8–10

    uses Nat.cast_le.mpr

      intro u v
      obtain ⟨w, hw⟩ := h u v
      exact w.edist_le.trans (Nat.cast_le.mpr hw)
ENat.toNat_le_of_le_natCast
For an extended natural number m and a natural number n, if m ≤ n (cast to ℕ∞), then m.toNat ≤ n.
G.ediam_le_iff
The extended diameter of a graph G is at most k (in ℕ∞) if and only if the extended distance between every pair of vertices in G is at most k.
Nat.cast_le.mpr
For natural numbers m and n, if m ≤ n, then the cast of m into ℕ∞ is at most the cast of 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

/-- If every pair of vertices in a simple graph has a walk of length at most D, the diameter is at most D. -/theorem simple_graph_diam_le_of_forall_exists_walk_le    {α : Type*} (G : SimpleGraph α) (D : ℕ)    (h : ∀ u v : α, ∃ w : G.Walk u v, w.length ≤ D) :    G.diam ≤ D := by  apply ENat.toNat_le_of_le_natCast  rw [G.ediam_le_iff]  intro u v  obtain ⟨w, hw⟩ := h u v  exact w.edist_le.trans (Nat.cast_le.mpr hw)
See it in the graphDiscuss this resultChallenge it