simple_graph_power_well_covered_not_ball_union_subset
Let 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) ⊆ B_d(w), where B_d(x) is the set of vertices at distance at most d from x.
Statement
theorem simple_graph_power_well_covered_not_ball_union_subset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hd : 1 ≤ d) (hwc : simple_graph_is_well_covered (simple_graph_power G d)) (s t w : V) (hst : ((d + 1 : ℕ) : ℕ∞) ≤ G.edist s t) : ¬ ∀ x : V, (G.edist s x ≤ d ∨ G.edist t x ≤ d) → G.edist w x ≤ d
- Formalizes
- arXiv:2610.09300 (On graphs whose powers are well-covered), Lemma 2.7. The proof uses well-coveredness directly (two maximal independent sets of different sizes) instead of the independence number.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- simple_graph_exists_maximal_indep_supersetIn a finite graph every independent set is contained in a maximal independent set.
- Used by 2
- bipartite_ravindra_matching_power_two_well_covered_diam_le_twoIf a finite connected bipartite simple graph G admits a perfect matching M with complete bipartite neighborhoods and its second power G^2…
- simple_graph_eccent_eq_diam_of_power_well_coveredLet 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…
The proof, explained
We argue by contradiction: suppose there exist vertices s, t, w with d_G(s, t) ≥ d + 1 such that B_d(s) ∪ B_d(t) ⊆ B_d(w). In the power graph P = G^d, the vertices s and t are non-adjacent and both are distinct from w. We extend {w} to a maximal independent set X in P, which cannot contain s or t since both are adjacent to w in P. Replacing w with {s, t} gives a new independent set Y = (X \ {w}) ∪ {s, t}, because any neighbor of s or t in X \ {w} would belong to B_d(s) ∪ B_d(t) ⊆ B_d(w) and thus be adjacent to w, contradicting the independence of X. Extending Y to a maximal independent set Z gives |Z| ≥ |Y| = |X| + 1, contradicting the hypothesis that P is well-covered.
Assume for contradiction that B_d(s) ∪ B_d(t) ⊆ B_d(w), and deduce that d_G(w, s) ≤ d and d_G(w, t) ≤ d.
We assume for contradiction that every vertex within distance d of s or t is within distance d of w (hball). We set P = simple_graph_power G d. Since d_G(s, s) = 0 ≤ d, vertex s is in B_d(s) and hence in B_d(w), showing d_G(w, s) ≤ d (hsw). Similarly, d_G(t, t) = 0 ≤ d implies d_G(w, t) ≤ d (htw).
intro hball set P := simple_graph_power G d have hsw : G.edist w s ≤ d := hball s (Or.inl (by simp)) have htw : G.edist w t ≤ d := hball t (Or.inr (by simp))
Show that distance at most d is incompatible with distance at least d + 1, and deduce that s, t, w are pairwise distinct.
First, having both d_G(x, y) ≤ d and d + 1 ≤ d_G(x, y) gives d + 1 ≤ d by transitivity, an impossibility (hlt). If s = t, then d_G(s, t) = 0 ≥ d + 1 ≥ 2, a contradiction; hence s ≠ t (hst_ne). If w = s, then d_G(s, t) = d_G(w, t) ≤ d, contradicting d_G(s, t) ≥ d + 1; hence w ≠ s (hws). Finally, if w = t, symmetry of distance (SimpleGraph.edist_comm) yields d_G(s, t) = d_G(s, w) = d_G(w, s) ≤ d, again contradicting d_G(s, t) ≥ d + 1; hence w ≠ t (hwt).
uses
SimpleGraph.edist_commhave hlt : ∀ x y : V, G.edist x y ≤ d → ¬ ((d + 1 : ℕ) : ℕ∞) ≤ G.edist x y := by intro x y h1 h2 have := h2.trans h1 norm_cast at this omega have hst_ne : s ≠ t := by intro h; subst h; simp at hst have hws : w ≠ s := by intro h; subst h; exact hlt w t htw hst have hwt : w ≠ t := by intro h; subst h; rw [SimpleGraph.edist_comm] at hsw; exact hlt s w hsw hst
Extend {w} to a maximal independent set X in P, and show that neither s nor t belongs to X.
Any vertex x ≠ w in B_d(s) ∪ B_d(t) has d_G(w, x) ≤ d and thus is adjacent to w in P (hadjw). The singleton {w} is independent in P, so it extends to a maximal independent set X with w ∈ X (simple_graph_exists_maximal_indep_superset, Finset.mem_singleton_self). Since s ≠ w and d_G(s, s) ≤ d, vertex s is adjacent to w in P; because X is independent and w ∈ X, we have s ∉ X (hsX). By the same argument for t, t ∉ X (htX).
uses
simple_graph_exists_maximal_indep_superset,Finset.mem_singleton_selfhave hadjw : ∀ x, x ≠ w → (G.edist s x ≤ d ∨ G.edist t x ≤ d) → P.Adj w x := fun x hx h => ⟨fun e => hx e.symm, hball x h⟩ obtain ⟨X, hwX, hX⟩ := simple_graph_exists_maximal_indep_superset P {w} (by simp) have hwX' : w ∈ X := hwX (Finset.mem_singleton_self w) have hsX : s ∉ X := fun h => hX.1 hwX' h hws (hadjw s hws.symm (Or.inl (by simp))) have htX : t ∉ X := fun h => hX.1 hwX' h hwt (hadjw t hwt.symm (Or.inr (by simp)))
The set Y = (X \ {w}) ∪ {s, t} is independent in P.
We check that no two distinct vertices in Y are adjacent in P. If some x ∈ X \ {w} were adjacent to y ∈ {s, t}, then d_G(y, x) ≤ d, placing x in B_d(s) ∪ B_d(t). Since x ≠ w, this would make x adjacent to w in P, which is impossible because both w, x ∈ X and X is independent (the helper lemma key). Vertices within X \ {w} are non-adjacent because X is independent (Finset.mem_of_mem_erase). Finally, s and t cannot be adjacent in P because d_G(s, t) ≥ d + 1 > d. Thus Y is an independent set in P.
uses
Finset.mem_erase,Finset.mem_insert,Finset.mem_singleton,Finset.coe_union,Set.mem_union,Finset.mem_coe,Finset.mem_of_mem_eraseset Y := X.erase w ∪ {s, t} have hYind : P.IsIndepSet (Y : Set V) := by have key : ∀ x ∈ X.erase w, ∀ y ∈ ({s, t} : Finset V), ¬ P.Adj y x := by intro x hx y hy hadj rw [Finset.mem_erase] at hx have hyx : G.edist y x ≤ d := hadj.2 simp only [Finset.mem_insert, Finset.mem_singleton] at hy have : P.Adj w x := by rcases hy with rfl | rfl · exact hadjw x hx.1 (Or.inl hyx) · exact hadjw x hx.1 (Or.inr hyx) exact hX.1 hwX' hx.2 (fun e => hx.1 e.symm) this intro x hx y hy hxy hadj simp only [Y, Finset.coe_union, Set.mem_union, Finset.mem_coe] at hx hy rcases hx with hx | hx <;> rcases hy with hy | hy · exact hX.1 (Finset.mem_of_mem_erase hx) (Finset.mem_of_mem_erase hy) hxy hadj · exact key x hx y hy hadj.symm · exact key y hy x hx hadj · simp only [Finset.mem_insert, Finset.mem_singleton] at hx hy have hst' : ¬ P.Adj s t := fun h => hlt s t h.2 hst rcases hx with rfl | rfl <;> rcases hy with rfl | rfl · exact hxy rfl · exact hst' hadj · exact hst' hadj.symm · exact hxy rfl
Extend Y to a maximal independent set Z in P, and show |Y| = |X| + 1.
The independent set Y extends to a maximal independent set Z in P (simple_graph_exists_maximal_indep_superset). Since neither s nor t is in X, the sets X \ {w} and {s, t} are disjoint (Finset.disjoint_left). The cardinality of their union is therefore |X \ {w}| + |{s, t}| (Finset.card_union_of_disjoint). Since w ∈ X, erasing w gives |X| - 1 (Finset.card_erase_of_mem), and because s ≠ t, |{s, t}| = 2 (Finset.card_pair). Thus |Y| = (|X| - 1) + 2 = |X| + 1.
uses
simple_graph_exists_maximal_indep_superset,Finset.disjoint_left,Finset.mem_insert,Finset.mem_singleton,Finset.mem_of_mem_erase,Finset.card_union_of_disjoint,Finset.card_erase_of_mem,Finset.card_pairobtain ⟨Z, hYZ, hZ⟩ := simple_graph_exists_maximal_indep_superset P Y hYind have hcardY : Y.card = X.card + 1 := by have hdisj : Disjoint (X.erase w) {s, t} := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_insert, Finset.mem_singleton] at hx' rcases hx' with rfl | rfl · exact hsX (Finset.mem_of_mem_erase hx) · exact htX (Finset.mem_of_mem_erase hx) rw [Finset.card_union_of_disjoint hdisj, Finset.card_erase_of_mem hwX', Finset.card_pair hst_ne] have : 1 ≤ X.card := Finset.card_pos.2 ⟨w, hwX'⟩ omega
Derive a contradiction: |Z| ≥ |X| + 1 contradicts well-coveredness, which requires |Z| = |X|.
Since Y ⊆ Z, we have |Y| ≤ |Z| (Finset.card_le_card), so |Z| ≥ |X| + 1. But P is well-covered (hwc), so all maximal independent sets have the same size, which forces |X| = |Z|. This gives |X| ≥ |X| + 1, an arithmetic impossibility that omega resolves to conclude False.
uses
Finset.card_le_cardhave h1 := Finset.card_le_card hYZ have h2 := hwc X Z hX hZ omega
SimpleGraph.edist_comm- Extended distance between vertices in a graph is symmetric: d_G(u, v) = d_G(v, u).
simple_graph_exists_maximal_indep_superset- Every independent set in a finite graph extends to an inclusion-maximal independent set.
Finset.mem_singleton_self- An element is a member of its own singleton set: a ∈ {a}.
Finset.mem_erase- An element is in s.erase b if and only if it is in s and distinct from b.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or is in s.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Finset.coe_union- The coercion of a union of finite sets to a Set equals the union of their coercions: ↑(s₁ ∪ s₂) = ↑s₁ ∪ ↑s₂.
Set.mem_union- An element belongs to a ∪ b if and only if it belongs to a or to b.
Finset.mem_coe- Membership in the coerced Set ↑s is equivalent to membership in the Finset s.
Finset.mem_of_mem_erase- If an element belongs to s.erase a, then it belongs to s.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.card_union_of_disjoint- If two finite sets are disjoint, the cardinality of their union is the sum of their cardinalities.
Finset.card_erase_of_mem- Removing an element a from a finite set s of which it is a member decreases its cardinality by 1.
Finset.card_pair- If two elements are distinct, the pair {a, b} has cardinality 2.
Finset.card_le_card- If s ⊆ t for finite sets, then |s| ≤ |t|.
- The power graph simple_graph_power G d defines an edge between distinct vertices u ≠ v whenever their extended distance G.edist u v in G is at most d.
- The helper lemma hlt casts distances from ℕ∞ to ℕ so that the contradictory inequality d + 1 ≤ d can be resolved by omega.
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_power_well_covered_not_ball_union_subset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (d : ℕ) (hd : 1 ≤ d) (hwc : simple_graph_is_well_covered (simple_graph_power G d)) (s t w : V) (hst : ((d + 1 : ℕ) : ℕ∞) ≤ G.edist s t) : ¬ ∀ x : V, (G.edist s x ≤ d ∨ G.edist t x ≤ d) → G.edist w x ≤ d := by intro hball set P := simple_graph_power G d have hsw : G.edist w s ≤ d := hball s (Or.inl (by simp)) have htw : G.edist w t ≤ d := hball t (Or.inr (by simp)) have hlt : ∀ x y : V, G.edist x y ≤ d → ¬ ((d + 1 : ℕ) : ℕ∞) ≤ G.edist x y := by intro x y h1 h2 have := h2.trans h1 norm_cast at this omega have hst_ne : s ≠ t := by intro h; subst h; simp at hst have hws : w ≠ s := by intro h; subst h; exact hlt w t htw hst have hwt : w ≠ t := by intro h; subst h; rw [SimpleGraph.edist_comm] at hsw; exact hlt s w hsw hst have hadjw : ∀ x, x ≠ w → (G.edist s x ≤ d ∨ G.edist t x ≤ d) → P.Adj w x := fun x hx h => ⟨fun e => hx e.symm, hball x h⟩ obtain ⟨X, hwX, hX⟩ := simple_graph_exists_maximal_indep_superset P {w} (by simp) have hwX' : w ∈ X := hwX (Finset.mem_singleton_self w) have hsX : s ∉ X := fun h => hX.1 hwX' h hws (hadjw s hws.symm (Or.inl (by simp))) have htX : t ∉ X := fun h => hX.1 hwX' h hwt (hadjw t hwt.symm (Or.inr (by simp))) set Y := X.erase w ∪ {s, t} have hYind : P.IsIndepSet (Y : Set V) := by have key : ∀ x ∈ X.erase w, ∀ y ∈ ({s, t} : Finset V), ¬ P.Adj y x := by intro x hx y hy hadj rw [Finset.mem_erase] at hx have hyx : G.edist y x ≤ d := hadj.2 simp only [Finset.mem_insert, Finset.mem_singleton] at hy have : P.Adj w x := by rcases hy with rfl | rfl · exact hadjw x hx.1 (Or.inl hyx) · exact hadjw x hx.1 (Or.inr hyx) exact hX.1 hwX' hx.2 (fun e => hx.1 e.symm) this intro x hx y hy hxy hadj simp only [Y, Finset.coe_union, Set.mem_union, Finset.mem_coe] at hx hy rcases hx with hx | hx <;> rcases hy with hy | hy · exact hX.1 (Finset.mem_of_mem_erase hx) (Finset.mem_of_mem_erase hy) hxy hadj · exact key x hx y hy hadj.symm · exact key y hy x hx hadj · simp only [Finset.mem_insert, Finset.mem_singleton] at hx hy have hst' : ¬ P.Adj s t := fun h => hlt s t h.2 hst rcases hx with rfl | rfl <;> rcases hy with rfl | rfl · exact hxy rfl · exact hst' hadj · exact hst' hadj.symm · exact hxy rfl obtain ⟨Z, hYZ, hZ⟩ := simple_graph_exists_maximal_indep_superset P Y hYind have hcardY : Y.card = X.card + 1 := by have hdisj : Disjoint (X.erase w) {s, t} := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_insert, Finset.mem_singleton] at hx' rcases hx' with rfl | rfl · exact hsX (Finset.mem_of_mem_erase hx) · exact htX (Finset.mem_of_mem_erase hx) rw [Finset.card_union_of_disjoint hdisj, Finset.card_erase_of_mem hwX', Finset.card_pair hst_ne] have : 1 ≤ X.card := Finset.card_pos.2 ⟨w, hwX'⟩ omega have h1 := Finset.card_le_card hYZ have h2 := hwc X Z hX hZ omega