AFTD Auto-Formalizing Theoretical Domains

simple_graph_eccent_eq_diam_of_power_well_covered

theoremverifiedformalization

Let G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then every vertex of G has eccentricity D (G is self-centered).

Statement

theorem simple_graph_eccent_eq_diam_of_power_well_covered {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (hconn : G.Connected) (hD : 2 ≤ G.diam)
    (hwc : simple_graph_is_well_covered (simple_graph_power G (G.diam - 1))) (v : V) :
    G.eccent v = G.diam
Formalizes
arXiv:2610.09300 (On graphs whose powers are well-covered), Lemma 2.5, for D ≥ 2 (for D ≤ 1 the power G^{D−1} is edgeless); proof via Lemma 2.7 (simple_graph_power_well_covered_not_ball_union_subset) with w the vertex of small eccentricity.
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • simple_graph_power_well_covered_not_ball_union_subsetLet G be a finite graph and d ≥ 1 with G^d well-covered. Then there are no vertices s, t, w with d_G(s, t) ≥ d + 1 and B_d(s) ∪ B_d(t) ⊆…
  • simple_graph_powerThe d-th power G^d of a graph G: same vertices, two distinct vertices adjacent iff they are joined by a path (equivalently a walk) of…
  • simple_graph_is_well_coveredA finite graph is well-covered if all its maximal independent sets have the same cardinality (equivalently, all its minimal vertex covers…
Used by 1

The proof, explained

By definition, the eccentricity of any vertex v is at most the diameter D. Supposing for contradiction that ecc(v) < D, the eccentricity must satisfy ecc(v) ≤ D − 1, which means the closed ball B_{D−1}(v) covers all vertices in the graph. In particular, choosing two vertices s and t at maximal distance D ≥ (D − 1) + 1, the ball B_{D−1}(v) would contain the union B_{D−1}(s) ∪ B_{D−1}(t); but this contradicts the structural theorem simple_graph_power_well_covered_not_ball_union_subset for well-covered powers of graphs.

  1. The extended diameter of G is finite and equals the diameter G.diam coerced to ℕ∞.

    Because G is connected, its vertex set is non-empty. For a finite connected graph, the extended diameter cannot be infinite (SimpleGraph.connected_iff_ediam_ne_top). By definition of the diameter G.diam as ediam.toNat, casting it back to ℕ∞ recovers the extended diameter via ENat.natCast_toNat.

    lines 5–8

    uses SimpleGraph.connected_iff_ediam_ne_top, SimpleGraph.diam, ENat.natCast_toNat

      have : Nonempty V := hconn.nonempty
      have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn
      have hdiam : (G.diam : ℕ∞) = G.ediam := by
        rw [SimpleGraph.diam]; exact ENat.natCast_toNat htop
  2. It suffices to show that G.diam ≤ G.eccent v.

    The eccentricity of v is always at most the graph diameter (G.eccent_le_ediam). By antisymmetry of ≤ (le_antisymm), equality reduces to the reverse inequality G.diam ≤ G.eccent v.

    line 9

    uses le_antisymm, G.eccent_le_ediam

      apply le_antisymm (hdiam ▸ G.eccent_le_ediam)
  3. Assuming the contrary, the eccentricity of v is a finite natural number e with e < G.diam.

    We assume for contradiction that G.diam ≤ G.eccent v is false, so G.eccent v < G.diam (not_le). Since it is strictly bounded by a finite value, the eccentricity cannot be ∞ (ne_top_of_lt), so it equals a natural number e (ENat.natCast_toNat) satisfying e < G.diam.

    lines 10–15

    uses not_le, ne_top_of_lt, ENat.natCast_toNat

      by_contra hlt
      rw [not_le] at hlt
      obtain ⟨e, he⟩ : ∃ e : ℕ, G.eccent v = e := ⟨(G.eccent v).toNat,
        (ENat.natCast_toNat (ne_top_of_lt hlt)).symm⟩
      rw [he] at hlt
      norm_cast at hlt
  4. There exist vertices s and t in G whose distance equals the diameter of G.

    Because G is finite, there exists a pair of vertices s and t attaining the diameter: dist(s, t) = ediam(G) (G.exists_edist_eq_ediam_of_finite).

    line 16

    uses G.exists_edist_eq_ediam_of_finite

      obtain ⟨s, t, hst⟩ := G.exists_edist_eq_ediam_of_finite
  5. The contradiction reduces to showing that dist(s, t) ≥ (G.diam − 1) + 1 and that the ball B_{D−1}(v) contains B_{D−1}(s) ∪ B_{D−1}(t).

    Since G.diam ≥ 2, setting d = G.diam − 1 gives d ≥ 1. By the lemma simple_graph_power_well_covered_not_ball_union_subset, when G^d is well-covered and dist(s, t) ≥ d + 1, no single ball of radius d can contain the union of the balls of radius d around s and t. Applying this lemma leaves two obligations: confirming the distance between s and t is at least d + 1, and showing every vertex in the union of the balls around s and t is within distance d of v.

    lines 17–18

    uses simple_graph_power_well_covered_not_ball_union_subset

      refine simple_graph_power_well_covered_not_ball_union_subset G (G.diam - 1) (by omega) hwc s t v
        ?_ ?_
  6. The distance between s and t is at least (G.diam − 1) + 1.

    By construction, dist(s, t) = ediam(G) = G.diam. The inequality (G.diam − 1) + 1 ≤ G.diam holds by standard arithmetic since G.diam ≥ 2.

    line 19

      · rw [hst, ← hdiam]; norm_cast; omega
  7. Every vertex in the graph lies within distance G.diam − 1 of v, completing the contradiction.

    For any vertex x, the distance dist(v, x) is bounded by the eccentricity ecc(v) (SimpleGraph.edist_le_eccent), which equals e. Since e < G.diam, we have e ≤ G.diam − 1, so every vertex x in G is within distance G.diam − 1 of v. In particular, B_{D−1}(v) contains B_{D−1}(s) ∪ B_{D−1}(t), contradicting the lemma.

    lines 20–23

    uses SimpleGraph.edist_le_eccent

      · intro x _
        calc G.edist v x ≤ G.eccent v := SimpleGraph.edist_le_eccent
          _ = e := he
          _ ≤ ((G.diam - 1 : ℕ) : ℕ∞) := by norm_cast; omega
SimpleGraph.connected_iff_ediam_ne_top
A finite non-empty graph is connected if and only if its extended diameter is not ∞.
SimpleGraph.diam
The natural-number diameter of a graph, defined by converting its extended diameter in ℕ∞ to ℕ.
ENat.natCast_toNat
For any element n of ℕ∞ with n ≠ ⊤, casting its conversion to ℕ back to ℕ∞ returns n.
le_antisymm
In a partial order, if a ≤ b and b ≤ a, then a = b.
G.eccent_le_ediam
The eccentricity of any vertex in a graph is at most the graph's extended diameter.
not_le
In a linear order, not being less than or equal to an element is equivalent to being strictly greater than it.
ne_top_of_lt
In a preorder with a top element ⊤, an element strictly smaller than another cannot be ⊤.
G.exists_edist_eq_ediam_of_finite
In a finite non-empty graph, there exists a pair of vertices whose distance equals the extended diameter.
simple_graph_power_well_covered_not_ball_union_subset
If the d-th power of a graph is well-covered (with d ≥ 1) and two vertices s, t are at distance at least d + 1, then no vertex w has its closed ball of radius d contain the union of the closed balls of radius d centered at s and t.
SimpleGraph.edist_le_eccent
The distance between any vertex u and another vertex v is at most the eccentricity of u.

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

theorem simple_graph_eccent_eq_diam_of_power_well_covered {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (hconn : G.Connected) (hD : 2 ≤ G.diam)    (hwc : simple_graph_is_well_covered (simple_graph_power G (G.diam - 1))) (v : V) :    G.eccent v = G.diam := by  have : Nonempty V := hconn.nonempty  have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn  have hdiam : (G.diam : ℕ∞) = G.ediam := by    rw [SimpleGraph.diam]; exact ENat.natCast_toNat htop  apply le_antisymm (hdiam ▸ G.eccent_le_ediam)  by_contra hlt  rw [not_le] at hlt  obtain ⟨e, he⟩ : ∃ e : ℕ, G.eccent v = e := ⟨(G.eccent v).toNat,    (ENat.natCast_toNat (ne_top_of_lt hlt)).symm⟩  rw [he] at hlt  norm_cast at hlt  obtain ⟨s, t, hst⟩ := G.exists_edist_eq_ediam_of_finite  refine simple_graph_power_well_covered_not_ball_union_subset G (G.diam - 1) (by omega) hwc s t v    ?_ ?_  · rw [hst, ← hdiam]; norm_cast; omega  · intro x _    calc G.edist v x ≤ G.eccent v := SimpleGraph.edist_le_eccent      _ = e := he      _ ≤ ((G.diam - 1 : ℕ) : ℕ∞) := by norm_cast; omega
See it in the graphDiscuss this resultChallenge it