AFTD Auto-Formalizing Theoretical Domains

forall_power_well_covered_iff_clique_blowup

theoremverifiedformalization

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.

  1. 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.

    lines 6–7

    uses forall_congr', imp_congr_right, simple_graph_power_well_covered_iff_clique_blowup

      forall_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
See it in the graphDiscuss this resultChallenge it