graph_dist_le_two_of_ediam_le_two
If the extended diameter of a graph is at most 2, then every (natural-valued) distance is at most 2.
Statement
theorem graph_dist_le_two_of_ediam_le_two {V : Type*} (G : SimpleGraph V) (hdiam : G.ediam ≤ 2) (u v : V) : G.dist u v ≤ 2
- Source
- step towards exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_ge
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- exists_idle_measure_wasserstein_dist_lt_one_of_ediam_le_two_and_minDegree_geIn a connected graph of diameter at most 2 with minimum degree at least 2n/3 − 1, for every edge xy there exists α ∈ (0, 1) such that the…
- graph_idle_transport_plan_main_costFor an edge xy in a graph of diameter at most 2, the main plan from μ_x^{1/2} to μ_y^{1/2} costs at most 1/2 − (1/2)/d_x + 2|B|·(1/2)/d_y.
- graph_idle_transport_plan_specialIf the edge partition has |A| = |B| ≥ 1, deg x = deg y, |B| = |C|+2 and an A–B edge, then μ_x^{1/2} and μ_y^{1/2} admit a plan of cost at…
The proof, explained
To show that every pairwise distance is at most 2, the proof first deduces that the extended diameter G.ediam is finite (not ⊤) from the hypothesis G.ediam ≤ 2. It then projects this bound from the extended natural numbers ℕ∞ to the natural numbers ℕ to show that G.diam ≤ 2. Finally, because the extended diameter is finite, every vertex-to-vertex distance is bounded by G.diam, which yields G.dist u v ≤ 2.
G.ediam ≠ ⊤
Assume for contradiction that G.ediam = ⊤. Rewriting with this assumption in G.ediam ≤ 2 gives ⊤ ≤ 2, which simplifies to False since infinity is strictly greater than 2.
have htop : G.ediam ≠ ⊤ := by intro h; rw [h] at hdiam; simp at hdiam
G.diam ≤ 2
Since G.ediam ≤ 2 and 2 ≠ ⊤ in ℕ∞, applying `ENat.toNat_le_toNat` yields G.ediam.toNat ≤ 2. Unfolding the definition of diameter (`SimpleGraph.diam`), which defines G.diam as G.ediam.toNat, simplifies this to G.diam ≤ 2.
uses
ENat.toNat_le_toNat,SimpleGraph.diamhave h2 : G.diam ≤ 2 := by have := ENat.toNat_le_toNat hdiam (by simp : (2 : ℕ∞) ≠ ⊤) simpa [SimpleGraph.diam] using this
G.dist u v ≤ 2
Because G.ediam ≠ ⊤, the distance between any two vertices u and v is at most the graph diameter (`SimpleGraph.dist_le_diam`), giving G.dist u v ≤ G.diam. Combining this with G.diam ≤ 2 via linear integer arithmetic (`omega`) finishes the proof.
uses
SimpleGraph.dist_le_diamhave := SimpleGraph.dist_le_diam htop (u := u) (v := v) omega
ENat.toNat_le_toNat- For extended natural numbers m, n ∈ ℕ∞, if m ≤ n and n ≠ ⊤, then their projections to ℕ satisfy m.toNat ≤ n.toNat.
SimpleGraph.diam- The diameter of a simple graph as a natural number, defined as the projection of its extended diameter G.ediam from ℕ∞ to ℕ.
SimpleGraph.dist_le_diam- In a simple graph with finite extended diameter (G.ediam ≠ ⊤), the distance between any two vertices u and v is at most the graph diameter G.diam.
- In Mathlib, distances and diameters come in two flavours: extended values in `ℕ∞` (`ediam`, `edist`) and natural values in `ℕ` (`diam`, `dist`). By convention, if a graph is disconnected, `ediam = ⊤` while `diam = 0`. As a result, the lemma `SimpleGraph.dist_le_diam` requires the hypothesis `G.ediam ≠ ⊤` to prevent counterexamples, which is why lines 4–5 explicitly prove finiteness.
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.
/-- Diameter at most 2 gives all distances at most 2. -/theorem graph_dist_le_two_of_ediam_le_two {V : Type*} (G : SimpleGraph V) (hdiam : G.ediam ≤ 2) (u v : V) : G.dist u v ≤ 2 := by have htop : G.ediam ≠ ⊤ := by intro h; rw [h] at hdiam; simp at hdiam have h2 : G.diam ≤ 2 := by have := ENat.toNat_le_toNat hdiam (by simp : (2 : ℕ∞) ≠ ⊤) simpa [SimpleGraph.diam] using this have := SimpleGraph.dist_le_diam htop (u := u) (v := v) omega