forall_power_well_covered_iff_clique_blowup
Let G be a finite simple graph and a_1, …, a_n positive integers, H = G[K_{a_1}, …, K_{a_n}] its clique blow-up. Then G^d is well-covered for all d ≥ 1 iff H^d is well-covered for all d ≥ 1.
Statement
theorem forall_power_well_covered_iff_clique_blowup {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) : (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) ↔ (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (simple_graph_clique_blowup G a) d))
- Formalizes
- arXiv:2610.09300 (On graphs whose powers are well-covered), Theorem 1.6.
- Verified
- 11 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- simple_graph_power_well_covered_iff_clique_blowupFor every d ≥ 1 and positive integers a_i, G^d is well-covered iff H^d is well-covered, where H = G[K_{a_1}, …, K_{a_n}].
- simple_graph_clique_blowupThe clique blow-up H = G[K_{a_1}, …, K_{a_n}]: each vertex v_i of G is replaced by a clique Q_i on a_i vertices, and distinct vertices x ∈…
- 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…
The proof, explained
The universal statement across all powers d ≥ 1 is reduced by logical congruence to the claim for an individual exponent d. For any fixed d ≥ 1, the theorem simple_graph_power_well_covered_iff_clique_blowup already establishes that G^d is well-covered if and only if the d-th power of the clique blow-up is well-covered. Applying universal and conditional congruence yields the equivalence for all d ≥ 1 simultaneously.
For all d ≥ 1, G^d is well-covered if and only if for all d ≥ 1, the d-th power of the clique blow-up is well-covered.
Universal quantifier congruence (forall_congr') and implication congruence (imp_congr_right) reduce the equivalence of the universally quantified assertions over d ≥ 1 to the pointwise equivalence for each fixed exponent d ≥ 1. That pointwise equivalence is supplied directly by simple_graph_power_well_covered_iff_clique_blowup applied to G, the weight function a, its positivity hypothesis ha, and the assumption hd that d ≥ 1.
uses
forall_congr',imp_congr_right,simple_graph_power_well_covered_iff_clique_blowupforall_congr' fun d => imp_congr_right fun hd => simple_graph_power_well_covered_iff_clique_blowup G a ha d hd
forall_congr'- Universally quantified statements are logically equivalent if their underlying predicates are pointwise equivalent for every argument.
imp_congr_right- Two implications with the same antecedent are equivalent if the antecedent implies that their consequents are equivalent.
simple_graph_power_well_covered_iff_clique_blowup- For a finite graph G and positive weights a, and any fixed power exponent d ≥ 1, the d-th power G^d is well-covered if and only if the d-th power of the clique blow-up G[K_a]^d is well-covered.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
theorem forall_power_well_covered_iff_clique_blowup {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) : (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) ↔ (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (simple_graph_clique_blowup G a) d)) := forall_congr' fun d => imp_congr_right fun hd => simple_graph_power_well_covered_iff_clique_blowup G a ha d hd