AFTD Auto-Formalizing Theoretical Domains

simple_graph_radius_ne_top_of_connected

theoremverified

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.

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

    lines 3–4

    uses SimpleGraph.radius_ne_top_iff.mpr

      haveI := 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).

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

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