simple_graph_radius_ne_top_of_connected
The radius of any finite connected simple graph is finite (not top in WithTop Nat).
Statement
theorem simple_graph_radius_ne_top_of_connected {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) : G.radius ≠ ⊤
- Source
- step towards radius_independence_connectivity_hamiltonian_interpolation
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
A connected graph on a finite vertex set is non-empty. For any finite, non-empty simple graph, Mathlib provides the equivalence that the graph has finite radius if and only if it is connected (`SimpleGraph.radius_ne_top_iff`). The result follows immediately by applying the reverse implication of this equivalence to the connectedness hypothesis.
The radius of G is finite (G.radius ≠ ⊤).
Since G is connected, its vertex set V is non-empty (via `hconn.nonempty`). For any finite, non-empty simple graph, connectedness implies that the radius is finite; applying `SimpleGraph.radius_ne_top_iff.mpr` to the connectedness hypothesis `hconn` immediately concludes the proof.
uses
SimpleGraph.radius_ne_top_iff.mprhaveI := hconn.nonempty exact SimpleGraph.radius_ne_top_iff.mpr hconn
SimpleGraph.radius_ne_top_iff.mpr- In a finite, non-empty simple graph, if the graph is connected, its radius is not ⊤ (i.e., it is finite).
- Mathlib's characterization `SimpleGraph.radius_ne_top_iff` requires an explicit `Nonempty` typeclass instance on the vertex type. Line 3 infers `Nonempty V` from the connectedness assumption `hconn` and adds it to the local instance cache before line 4 applies the lemma.
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.
/-- The radius of a finite connected simple graph is finite. -/theorem simple_graph_radius_ne_top_of_connected {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) : G.radius ≠ ⊤ := by haveI := hconn.nonempty exact SimpleGraph.radius_ne_top_iff.mpr hconn