simple_graph_eccent_eq_diam_of_power_well_covered
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
- simple_graph_no_leaf_of_power_well_coveredLet G be a finite connected graph of diameter D ≥ 2 such that G^{D−1} is well-covered. Then G has no leaves (no vertex of degree 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.
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.
uses
SimpleGraph.connected_iff_ediam_ne_top,SimpleGraph.diam,ENat.natCast_toNathave : 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
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.
uses
le_antisymm,G.eccent_le_ediamapply le_antisymm (hdiam ▸ G.eccent_le_ediam)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.
uses
not_le,ne_top_of_lt,ENat.natCast_toNatby_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
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).
uses
G.exists_edist_eq_ediam_of_finiteobtain ⟨s, t, hst⟩ := G.exists_edist_eq_ediam_of_finiteThe 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.
uses
simple_graph_power_well_covered_not_ball_union_subsetrefine simple_graph_power_well_covered_not_ball_union_subset G (G.diam - 1) (by omega) hwc s t v ?_ ?_
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.
· rw [hst, ← hdiam]; norm_cast; omega
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.
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.
- Coercions between ℕ and ℕ∞ are handled formally by ENat.natCast_toNat and norm_cast.
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.
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