AFTD Auto-Formalizing Theoretical Domains

graph_dist_le_two_of_ediam_le_two

theoremverified

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

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.

  1. 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.

    lines 4–5

      have htop : G.ediam ≠ ⊤ := by
        intro h; rw [h] at hdiam; simp at hdiam
  2. 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.

    lines 6–8

    uses ENat.toNat_le_toNat, SimpleGraph.diam

      have h2 : G.diam ≤ 2 := by
        have := ENat.toNat_le_toNat hdiam (by simp : (2 : ℕ∞) ≠ ⊤)
        simpa [SimpleGraph.diam] using this
  3. 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.

    lines 9–10

    uses SimpleGraph.dist_le_diam

      have := 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.

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

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