simple_graph_diam_le_of_forall_exists_walk_le
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
- simple_graph_reconfiguration_diam_le_three_halves_of_bipartiteLet G be a finite bipartite simple graph on a type V with decidable equality and decidable adjacency. For every integer k ≥ G.maxDegree +…
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.
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.
uses
ENat.toNat_le_of_le_natCast,G.ediam_le_iffapply ENat.toNat_le_of_le_natCast rw [G.ediam_le_iff]
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`).
uses
Nat.cast_le.mprintro 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.
- In Lean, `G.diam` is defined as `G.ediam.toNat`, where the extended diameter `G.ediam` takes values in `ℕ∞` (with ∞ mapping to 0 in `ℕ`). Line 6 bridges the diameter bound to a bound on the extended diameter.
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.
/-- 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)