AFTD Auto-Formalizing Theoretical Domains

simple_graph_radius_eq_one_imp_exists_universal

theoremverified

Any finite simple graph of radius 1 contains a universal vertex (adjacent to all other vertices).

Statement

theorem simple_graph_radius_eq_one_imp_exists_universal {V : Type*} [Fintype V] (G : SimpleGraph V) (hrad : G.radius = 1) : ∃ v : V, ∀ w : V, w ≠ v → G.Adj v w
Source
step towards radius_independence_connectivity_hamiltonian_interpolation
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To show that a finite simple graph G of radius 1 has a universal vertex, we first deduce that the vertex set cannot be empty, as an empty graph has infinite radius (⊤ ≠ 1). Since the graph is finite and nonempty, there exists a vertex u realizing the radius, so u has eccentricity 1. Vertices of eccentricity at most 1 are precisely those adjacent to all other vertices, making u the required universal vertex.

  1. The vertex set V is nonempty.

    Suppose for contradiction that V is empty (via `not_nonempty_iff.mp`). Then by `SimpleGraph.radius_eq_top_of_isEmpty`, the radius of G must be ⊤. But G has radius 1 by assumption, which yields the contradiction ⊤ = 1, closed by `simp`.

    lines 3–7

    uses not_nonempty_iff.mp, SimpleGraph.radius_eq_top_of_isEmpty

      have hne : Nonempty V := by
        by_contra h
        have hem : IsEmpty V := not_nonempty_iff.mp h
        rw [SimpleGraph.radius_eq_top_of_isEmpty (α := V) (G := G)] at hrad
        simp at hrad
  2. There exists a vertex u ∈ V whose eccentricity equals the radius of G (namely 1).

    Because V is nonempty and finite, there exists a central vertex u achieving the minimum eccentricity defining the radius, giving G.eccent u = G.radius = 1 by `G.exists_eccent_eq_radius`.

    line 8

    uses G.exists_eccent_eq_radius

      obtain ⟨u, hu⟩ := G.exists_eccent_eq_radius
  3. The vertex u is universal: it is adjacent to every other vertex w ≠ u.

    We provide u as the universal vertex. For any vertex w with w ≠ u, we have u ≠ w by `Ne.symm`. By `G.eccent_le_one_iff`, a vertex has eccentricity at most 1 if and only if it is adjacent to all other vertices. Since the eccentricity of u is 1 ≤ 1, u is adjacent to w.

    lines 9–10

    uses G.eccent_le_one_iff, Ne.symm

      refine ⟨u, fun w hw => ?_⟩
      exact G.eccent_le_one_iff u |>.mp (by rw [hu, hrad]) w (Ne.symm hw)
not_nonempty_iff.mp
A type is empty if and only if it is not nonempty; the `.mp` direction deduces `IsEmpty α` from `¬Nonempty α`.
SimpleGraph.radius_eq_top_of_isEmpty
The radius of a simple graph with an empty vertex set is ⊤ (infinity).
G.exists_eccent_eq_radius
In any nonempty finite simple graph, there exists a vertex whose eccentricity equals the graph's radius.
G.eccent_le_one_iff
The eccentricity of a vertex u is at most 1 if and only if u is adjacent to every distinct vertex v.
Ne.symm
Symmetry of disequality: if a ≠ b, then b ≠ a.

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

/-- A finite simple graph of radius 1 has a universal vertex. -/theorem simple_graph_radius_eq_one_imp_exists_universal {V : Type*} [Fintype V] (G : SimpleGraph V) (hrad : G.radius = 1) : ∃ v : V, ∀ w : V, w ≠ v → G.Adj v w := by  have hne : Nonempty V := by    by_contra h    have hem : IsEmpty V := not_nonempty_iff.mp h    rw [SimpleGraph.radius_eq_top_of_isEmpty (α := V) (G := G)] at hrad    simp at hrad  obtain ⟨u, hu⟩ := G.exists_eccent_eq_radius  refine ⟨u, fun w hw => ?_⟩  exact G.eccent_le_one_iff u |>.mp (by rw [hu, hrad]) w (Ne.symm hw)
See it in the graphDiscuss this resultChallenge it