forall_power_well_covered_of_well_covered_diam_le_three
Let G be a finite connected simple graph of diameter at most 3. If G and its second power G^2 are both well-covered, then every positive integer power G^d (for d ≥ 1) is well-covered.
Statement
theorem forall_power_well_covered_of_well_covered_diam_le_three {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 3) (hwc1 : simple_graph_is_well_covered G) (hwc2 : simple_graph_is_well_covered (simple_graph_power G 2)) : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)
- Source
- arXiv:2610.09300; OP-537
- Verified
- 27 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- simple_graph_power_oneG^1 = G.
- Used by 1
- exists_triangle_free_all_powers_well_covered_diam_eq_threeThere exists a finite connected triangle-free simple graph G with at least two vertices whose diameter is exactly 3 and such that every…
Read back from the Lean
Let $V$ be a finite type, and let $G$ be a simple graph on $V$. Assume that:
1. $G$ is connected (G.Connected),
2. The diameter of $G$ is at most 3 (G.diam ≤ 3),
3. $G$ is well-covered (simple_graph_is_well_covered G), and
4. The second power graph of $G$, $G^2$ (simple_graph_power G 2), is well-covered.
Then for every natural number $d \ge 1$, the $d$-th power graph $G^d$ (simple_graph_power G d) is well-covered.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To show that every power Gᵈ (for d ≥ 1) of a connected graph G with diameter at most 3 is well-covered, the argument splits into cases on the exponent d. For d = 1 and d = 2, well-coveredness holds by assumption since G¹ = G. For d ≥ 3, any two distinct vertices in G are at distance at most diam(G) ≤ 3 ≤ d, so the power graph Gᵈ coincides with the complete graph. Finally, the complete graph is shown to be well-covered because its maximal independent sets are precisely the singletons, which concludes the proof.
A finite subset of vertices is an independent set in the complete graph if and only if its cardinality is at most 1.
In the complete graph ⊤, every pair of distinct vertices is adjacent. An independent set cannot contain two distinct vertices, so any two elements in it must be equal; by Finset.card_le_one, this is equivalent to having cardinality at most 1. Conversely, if a set has at most one element, it contains no pairs of distinct vertices, so no two vertices in it are adjacent, making it independent.
uses
Finset.card_le_oneconstructor · intro h rw [Finset.card_le_one] intro a ha b hb by_contra hab exact (h ha hb hab) hab · intro h rw [Finset.card_le_one] at h intro a ha b hb hab exact fun hne => hne (h a ha b hb)
In the complete graph on a nonempty vertex set, every maximal independent set has cardinality 1.
By forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff, any independent set s satisfies |s| ≤ 1. If s were empty, choosing any vertex v from the nonempty vertex set would yield a singleton {v}, which is independent and strictly contains ∅ = s (via Finset.empty_subset), contradicting the maximality of s. Hence s is nonempty (Finset.card_pos, Finset.not_nonempty_iff_eq_empty), giving |s| > 0. Together with |s| ≤ 1, this forces |s| = 1.
uses
forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff,Finset.card_pos,Finset.not_nonempty_iff_eq_empty,Finset.empty_subsethave hle : s.card ≤ 1 := forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff s |>.mp hs.1 have hpos : 0 < s.card := by rw [Finset.card_pos] by_contra hne rw [Finset.not_nonempty_iff_eq_empty] at hne obtain ⟨v⟩ := ‹Nonempty V› have ht : (⊤ : SimpleGraph V).IsIndepSet (↑({v} : Finset V)) := by rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff]; simp have hsub : s ≤ ({v} : Finset V) := by rw [hne]; exact Finset.empty_subset _ have hle2 : ({v} : Finset V) ≤ s := hs.2 ht hsub have hv : v ∈ s := hle2 (by simp) rw [hne] at hv simp at hv omega
The complete graph on a finite nonempty vertex set is well-covered.
A graph is well-covered if all its maximal independent sets have the same cardinality. For the complete graph, any two maximal independent sets s and t each have cardinality 1 by forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one, so |s| = |t|.
uses
forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_oneintro s t hs ht rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one s hs, forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one t ht]
The vertex set of G is nonempty and the extended diameter of G is finite.
Because G is connected, its vertex set contains at least one vertex, and its extended diameter is finite (SimpleGraph.connected_iff_ediam_ne_top.mp).
uses
SimpleGraph.connected_iff_ediam_ne_top.mphaveI : Nonempty V := hconn.nonempty have hne_ediam : G.ediam ≠ ⊤ := SimpleGraph.connected_iff_ediam_ne_top.mp hconnFor every integer d ≥ 3, the graph power Gᵈ is the complete graph.
Two distinct vertices u and v are adjacent in Gᵈ if their distance in G is at most d. Since G is connected, u and v are reachable, so their distance is finite (SimpleGraph.edist_ne_top_iff_reachable.mpr). The distance between u and v is bounded by the graph diameter (SimpleGraph.edist_le_ediam, ENat.toNat_le_toNat), which is at most 3 by hypothesis. Since 3 ≤ d, transitivity (le_trans) gives dist_G(u, v) ≤ d. Thus all pairs of distinct vertices are adjacent in Gᵈ, showing Gᵈ = ⊤.
uses
SimpleGraph.edist_ne_top_iff_reachable.mpr,ENat.toNat_le_toNat,SimpleGraph.edist_le_ediam,ENat.natCast_toNat_eq_self.mpr,le_transhave htop : ∀ d : ℕ, 3 ≤ d → simple_graph_power G d = ⊤ := by intro d hd ext u v constructor · intro h; exact h.1 · intro huv refine ⟨huv, ?_⟩ have hreach : G.Reachable u v := hconn u v have hne : G.edist u v ≠ ⊤ := SimpleGraph.edist_ne_top_iff_reachable.mpr hreach have htoNat : (G.edist u v).toNat ≤ G.diam := ENat.toNat_le_toNat SimpleGraph.edist_le_ediam hne_ediam have heq : G.edist u v = ((G.edist u v).toNat : ℕ∞) := (ENat.natCast_toNat_eq_self.mpr hne).symm rw [heq] have hle : (G.edist u v).toNat ≤ d := le_trans htoNat (le_trans hdiam hd) exact_mod_cast hle
The graph power Gᵈ is well-covered when d = 1 or d = 2, and the case d = 0 is ruled out.
We perform case analysis on d. The case d = 0 contradicts the hypothesis 1 ≤ d and is closed by linear arithmetic. For d = 1, the power graph G¹ equals G by simple_graph_power_one, which is well-covered by hypothesis. For d = 2, G² is well-covered directly by hypothesis.
uses
simple_graph_power_oneintro d hd rcases d with _ | _ | _ | k · omega · rw [simple_graph_power_one]; exact hwc1 · exact hwc2
For every d ≥ 3, the graph power Gᵈ is well-covered.
For d ≥ 3, writing d = k + 3, the power graph Gᵏ⁺³ equals the complete graph ⊤. Because the complete graph on a finite nonempty vertex set is well-covered (forall_power_well_covered_of_well_covered_diam_le_three_aux_top), Gᵈ is well-covered.
uses
forall_power_well_covered_of_well_covered_diam_le_three_aux_top· have htopd : simple_graph_power G (k + 3) = ⊤ := htop (k + 3) (by omega) rw [htopd] exact forall_power_well_covered_of_well_covered_diam_le_three_aux_top
Finset.card_le_one- A finite set has cardinality at most 1 if and only if any two of its elements are equal.
forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff- A finite subset of vertices is an independent set in the complete graph if and only if its cardinality is at most 1.
Finset.card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
Finset.not_nonempty_iff_eq_empty- A finite set is not nonempty if and only if it is equal to the empty set.
Finset.empty_subset- The empty set is a subset of any finite set.
forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one- In the complete graph on a nonempty vertex set, every maximal independent set has cardinality 1.
forall_power_well_covered_of_well_covered_diam_le_three_aux_top- The complete graph on a finite nonempty vertex set is well-covered.
SimpleGraph.connected_iff_ediam_ne_top.mp- If a graph is connected, its extended diameter is not infinite.
SimpleGraph.edist_ne_top_iff_reachable.mpr- If two vertices are reachable from one another in a graph, their extended distance is not infinite.
SimpleGraph.edist_le_ediam- The extended distance between any two vertices in a graph is at most the extended diameter of the graph.
ENat.toNat_le_toNat- If an extended natural number m is at most an extended natural number n, and n is finite, then the natural number conversion of m is at most that of n.
ENat.natCast_toNat_eq_self.mpr- If an extended natural number is not infinite, embedding its natural number conversion back into the extended natural numbers yields the original value.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
simple_graph_power_one- The first power of a graph G¹ is equal to G.
- Graph distances in Lean take values in the extended natural numbers ℕ∞ = ℕ ∪ {∞}, requiring explicit conversions to ordinary natural numbers once reachability ensures finiteness.
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.
private lemma forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff {V : Type*} (s : Finset V) : (⊤ : SimpleGraph V).IsIndepSet (↑s) ↔ s.card ≤ 1 := by constructor · intro h rw [Finset.card_le_one] intro a ha b hb by_contra hab exact (h ha hb hab) hab · intro h rw [Finset.card_le_one] at h intro a ha b hb hab exact fun hne => hne (h a ha b hb)private lemma forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one {V : Type*} [Nonempty V] (s : Finset V) (hs : Maximal (fun u : Finset V => (⊤ : SimpleGraph V).IsIndepSet (↑u)) s) : s.card = 1 := by have hle : s.card ≤ 1 := forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff s |>.mp hs.1 have hpos : 0 < s.card := by rw [Finset.card_pos] by_contra hne rw [Finset.not_nonempty_iff_eq_empty] at hne obtain ⟨v⟩ := ‹Nonempty V› have ht : (⊤ : SimpleGraph V).IsIndepSet (↑({v} : Finset V)) := by rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_indep_top_iff]; simp have hsub : s ≤ ({v} : Finset V) := by rw [hne]; exact Finset.empty_subset _ have hle2 : ({v} : Finset V) ≤ s := hs.2 ht hsub have hv : v ∈ s := hle2 (by simp) rw [hne] at hv simp at hv omegaprivate lemma forall_power_well_covered_of_well_covered_diam_le_three_aux_top {V : Type*} [Fintype V] [Nonempty V] : simple_graph_is_well_covered (⊤ : SimpleGraph V) := by intro s t hs ht rw [forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one s hs, forall_power_well_covered_of_well_covered_diam_le_three_aux_top_card_eq_one t ht]/-- A connected graph of diameter at most 3 has all powers well-covered if G and G^2 are well-covered. -/theorem forall_power_well_covered_of_well_covered_diam_le_three {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hdiam : G.diam ≤ 3) (hwc1 : simple_graph_is_well_covered G) (hwc2 : simple_graph_is_well_covered (simple_graph_power G 2)) : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d) := by haveI : Nonempty V := hconn.nonempty have hne_ediam : G.ediam ≠ ⊤ := SimpleGraph.connected_iff_ediam_ne_top.mp hconn have htop : ∀ d : ℕ, 3 ≤ d → simple_graph_power G d = ⊤ := by intro d hd ext u v constructor · intro h; exact h.1 · intro huv refine ⟨huv, ?_⟩ have hreach : G.Reachable u v := hconn u v have hne : G.edist u v ≠ ⊤ := SimpleGraph.edist_ne_top_iff_reachable.mpr hreach have htoNat : (G.edist u v).toNat ≤ G.diam := ENat.toNat_le_toNat SimpleGraph.edist_le_ediam hne_ediam have heq : G.edist u v = ((G.edist u v).toNat : ℕ∞) := (ENat.natCast_toNat_eq_self.mpr hne).symm rw [heq] have hle : (G.edist u v).toNat ≤ d := le_trans htoNat (le_trans hdiam hd) exact_mod_cast hle intro d hd rcases d with _ | _ | _ | k · omega · rw [simple_graph_power_one]; exact hwc1 · exact hwc2 · have htopd : simple_graph_power G (k + 3) = ⊤ := htop (k + 3) (by omega) rw [htopd] exact forall_power_well_covered_of_well_covered_diam_le_three_aux_top