forall_power_well_covered_of_well_covered_diam_le_two
Let G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.
Statement
theorem forall_power_well_covered_of_well_covered_diam_le_two {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 2) (hwc : simple_graph_is_well_covered G) : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)
- Formalizes
- arXiv:2610.09300 (On graphs whose powers are well-covered), Sec. 3, remark before Question 3.9 ('every well-covered graph of diameter 2 automatically satisfies this condition'); stated for diameter at most 2.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_power_oneG^1 = G.
- 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_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…
- Used by 4
- op_1058_of_diam_le_twoFor any finite connected simple graphs G and H of diameter at most 2, if at least one of G and H is well-covered, then at least one of G…
- cycle_five_all_powers_well_coveredFor every positive integer d, the d-th power of the 5-cycle graph C_5 is well-covered.
- not_planar_all_powers_well_covered_characterizationIt is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is…
- complete_graph_two_all_powers_well_coveredThe complete graph on 2 vertices K_2 is connected, has diameter 1, and every positive power K_2^d (d ≥ 1) is well-covered.
The proof, explained
To show that G^d is well-covered for all d ≥ 1, the proof splits into two cases: d = 1 and d ≥ 2. When d = 1, the power graph G^1 is G itself, which is well-covered by hypothesis. When d ≥ 2, the assumption diam(G) ≤ 2 implies that every pair of distinct vertices has distance at most d and is therefore adjacent in G^d. Consequently, G^d is a complete graph, so every maximal independent set has size exactly 1, proving that G^d is well-covered.
For d = 1, the power graph G^1 is well-covered.
We introduce the exponent d ≥ 1 and divide into cases d < 2 and d ≥ 2. In the case d < 2, linear arithmetic implies d = 1. The first power G^1 is identically G, so well-coveredness follows immediately from the assumption that G is well-covered.
uses
Nat.lt_or_ge,simple_graph_power_oneintro d hd rcases Nat.lt_or_ge d 2 with h1 | h2 · have : d = 1 := by omega subst this rw [simple_graph_power_one] exact hwc
When d ≥ 2, the distance in G between any two vertices is at most d.
For d ≥ 2, graph connectedness implies the vertex set V is nonempty and the extended diameter ediam(G) is finite. The distance between any two vertices u, v ∈ V is at most ediam(G), which equals diam(G) because the extended diameter is finite. Since diam(G) ≤ 2 ≤ d, the distance between u and v is at most d.
uses
SimpleGraph.connected_iff_ediam_ne_top,SimpleGraph.edist_le_ediam,SimpleGraph.diam,ENat.natCast_toNat· have : Nonempty V := hconn.nonempty have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn have hed : ∀ u v : V, G.edist u v ≤ d := by intro u v calc G.edist u v ≤ G.ediam := SimpleGraph.edist_le_ediam _ = G.diam := by rw [SimpleGraph.diam]; exact (ENat.natCast_toNat htop).symm _ ≤ d := by exact_mod_cast hdiam.trans h2
When d ≥ 2, every maximal independent set in G^d has cardinality 1.
Let s be a maximal independent set in G^d. To show |s| = 1, we show s = {a} for some vertex a. If s were empty, any singleton {v} from the nonempty vertex set would be an independent set, contradicting the maximality of ∅. Thus s is nonempty, containing some vertex a. If s contained another vertex b ≠ a, then since dist(b, a) ≤ d, vertices b and a would be adjacent in G^d, contradicting that s is independent. Hence a is the unique element of s, so s = {a} and |s| = 1.
uses
Finset.card_eq_one,Finset.eq_singleton_iff_unique_mem,Finset.not_nonempty_iff_eq_empty,Finset.empty_subsethave hcard : ∀ s : Finset V, Maximal (fun u : Finset V => (simple_graph_power G d).IsIndepSet (u : Set V)) s → s.card = 1 := by intro s hs rw [Finset.card_eq_one] obtain ⟨v⟩ := ‹Nonempty V› by_cases hne : s.Nonempty · obtain ⟨a, ha⟩ := hne refine ⟨a, Finset.eq_singleton_iff_unique_mem.2 ⟨ha, fun b hb => ?_⟩⟩ by_contra hba exact hs.1 hb ha hba ⟨hba, hed b a⟩ · rw [Finset.not_nonempty_iff_eq_empty] at hne subst hne have hv : (simple_graph_power G d).IsIndepSet (({v} : Finset V) : Set V) := by simp have := hs.2 hv (Finset.empty_subset _) simp at this
When d ≥ 2, G^d is well-covered.
Given two maximal independent sets s and t of G^d, each has cardinality 1 by the previous step. Thus |s| = |t| = 1, which proves that G^d is well-covered.
intro s t hs ht rw [hcard s hs, hcard t ht]
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
simple_graph_power_one- The first power of a simple graph G is equal to G itself.
SimpleGraph.connected_iff_ediam_ne_top- A nonempty finite graph is connected if and only if its extended diameter is not infinite (⊤).
SimpleGraph.edist_le_ediam- The extended distance between any two vertices in a graph is bounded by its extended diameter.
SimpleGraph.diam- The definition of graph diameter as the natural number value of the extended diameter.
ENat.natCast_toNat- Casting a finite extended natural number to a natural number and back yields the original value.
Finset.card_eq_one- A finite set has cardinality 1 if and only if it is a singleton {a}.
Finset.eq_singleton_iff_unique_mem- A finite set s equals {a} if and only if a ∈ s and every element of s equals a.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is empty.
Finset.empty_subset- The empty set is a subset of any finite set.
- In the formal proof, the graph diameter is represented both as an extended natural number (ediam ∈ ℕ∞) and as a natural number (diam ∈ ℕ). Equating them requires explicitly verifying that ediam ≠ ⊤ via connectedness.
- When d ≥ 2 and diam(G) ≤ 2, every pair of distinct vertices in G has distance at most d, so the power graph G^d is the complete graph on V, whose only non-empty independent sets are singletons.
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 forall_power_well_covered_of_well_covered_diam_le_two {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 2) (hwc : simple_graph_is_well_covered G) : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by intro d hd rcases Nat.lt_or_ge d 2 with h1 | h2 · have : d = 1 := by omega subst this rw [simple_graph_power_one] exact hwc · have : Nonempty V := hconn.nonempty have htop : G.ediam ≠ ⊤ := (SimpleGraph.connected_iff_ediam_ne_top).1 hconn have hed : ∀ u v : V, G.edist u v ≤ d := by intro u v calc G.edist u v ≤ G.ediam := SimpleGraph.edist_le_ediam _ = G.diam := by rw [SimpleGraph.diam]; exact (ENat.natCast_toNat htop).symm _ ≤ d := by exact_mod_cast hdiam.trans h2 have hcard : ∀ s : Finset V, Maximal (fun u : Finset V => (simple_graph_power G d).IsIndepSet (u : Set V)) s → s.card = 1 := by intro s hs rw [Finset.card_eq_one] obtain ⟨v⟩ := ‹Nonempty V› by_cases hne : s.Nonempty · obtain ⟨a, ha⟩ := hne refine ⟨a, Finset.eq_singleton_iff_unique_mem.2 ⟨ha, fun b hb => ?_⟩⟩ by_contra hba exact hs.1 hb ha hba ⟨hba, hed b a⟩ · rw [Finset.not_nonempty_iff_eq_empty] at hne subst hne have hv : (simple_graph_power G d).IsIndepSet (({v} : Finset V) : Set V) := by simp have := hs.2 hv (Finset.empty_subset _) simp at this intro s t hs ht rw [hcard s hs, hcard t ht]