AFTD Auto-Formalizing Theoretical Domains

simple_graph_power_well_covered_iff_clique_blowup

theoremverified

For 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}].

Statement

theorem simple_graph_power_well_covered_iff_clique_blowup {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) (d : ℕ) (hd : 1 ≤ d) :
    simple_graph_is_well_covered (simple_graph_power G d) ↔
      simple_graph_is_well_covered (simple_graph_power (simple_graph_clique_blowup G a) d)
Source
The per-d form of the argument proving arXiv:2610.09300 (On graphs whose powers are well-covered), Theorem 1.6 (Claim 2 there: maximal independent sets of H^d are exactly one vertex from Q_i for each v_i in a maximal independent set of G^d).
Verified
11 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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_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_clique_blowup_edistIn the clique blow-up H of G, two vertices x ∈ Q_i and y ∈ Q_j with i ≠ j are at the same distance in H as v_i and v_j in G (including…
Used by 1

The proof, explained

For any graph G, positive weights a_i, and d ≥ 1, the d-th graph power G^d is well-covered if and only if the d-th power of the clique blowup H = G[K_{a_1}, …, K_{a_n}] is well-covered. The argument hinges on the fact that two vertices in H are adjacent in H^d if and only if they are distinct and either belong to the same clique fiber or project to adjacent vertices in G^d. As a result, independent sets in H^d correspond to independent sets in G^d via projection, which induces a size-preserving bijection between maximal independent sets in H^d and maximal independent sets in G^d. Well-coveredness (every maximal independent set having the same cardinality) therefore transfers directly between G^d and H^d.

  1. Two vertices p and q in the clique blowup H are adjacent in the graph power H^d if and only if p ≠ q and either they share the same base vertex (p.1 = q.1) or their projections are adjacent in G^d.

    Unfolding the definition of the graph power, adjacency means p ≠ q and the distance d_H(p, q) ≤ d. If p.1 = q.1 with p ≠ q, then p and q are adjacent in the clique fiber, giving d_H(p, q) = 1 ≤ d. If p.1 ≠ q.1, simple_graph_clique_blowup_edist equates d_H(p, q) with d_G(p.1, q.1), so d_H(p, q) ≤ d is equivalent to adjacency in G^d.

    lines 5–16

    uses simple_graph_clique_blowup_edist

      simp only [simple_graph_power]
      constructor
      · rintro ⟨hne, hle⟩
        refine ⟨hne, ?_⟩
        by_cases h : p.1 = q.1
        · exact Or.inl h
        · right; exact ⟨h, by rwa [← simple_graph_clique_blowup_edist G a ha p q h]⟩
      · rintro ⟨hne, h | ⟨h1, h2⟩⟩
        · refine ⟨hne, ?_⟩
          have hadj : (simple_graph_clique_blowup G a).Adj p q := Or.inl ⟨h, hne⟩
          rw [SimpleGraph.edist_eq_one_iff_adj.2 hadj]; exact_mod_cast hd
        · exact ⟨hne, by rwa [simple_graph_clique_blowup_edist G a ha p q h1]⟩
  2. A subset I of vertices of H is independent in H^d if and only if the projection π : (i, x) ↦ i is injective on I and the projected set π(I) is independent in G^d.

    Using the adjacency criterion hA for H^d: if I is independent, any two distinct vertices in I cannot share the same base vertex (which would make them adjacent in H^d), proving injectivity of π on I; nor can their projections be adjacent in G^d (which would also make them adjacent in H^d), showing π(I) is independent in G^d. Conversely, if π is injective on I and π(I) is independent in G^d, no two distinct vertices of I can be adjacent in H^d.

    lines 22–45

    uses simple_graph_clique_blowup_power_adj_iff

      set Gd := simple_graph_power G d
      set Hd := simple_graph_power (simple_graph_clique_blowup G a) d
      have hA := simple_graph_clique_blowup_power_adj_iff G a ha d hd
      -- independence in Hd
      have indep_iff : ∀ I : Finset (Σ i, Fin (a i)), Hd.IsIndepSet (I : Set (Σ i, Fin (a i))) ↔
          (Set.InjOn (Sigma.fst : (Σ i, Fin (a i)) → V) (I : Set (Σ i, Fin (a i))) ∧ Gd.IsIndepSet ((I.image Sigma.fst : Finset V) : Set V)) := by
        intro I
        constructor
        · intro hI
          refine ⟨fun x hx y hy hxy => ?_, ?_⟩
          · by_contra hne
            exact hI hx hy hne ((hA x y).2 ⟨hne, Or.inl hxy⟩)
          · intro i hi j hj hij hadj
            simp only [Finset.coe_image, Set.mem_image, Finset.mem_coe] at hi hj
            obtain ⟨x, hx, rfl⟩ := hi
            obtain ⟨y, hy, rfl⟩ := hj
            have hne : x ≠ y := fun e => hij (e ▸ rfl)
            exact hI hx hy hne ((hA x y).2 ⟨hne, Or.inr hadj⟩)
        · rintro ⟨hinj, hJ⟩ x hx y hy hne hadj
          obtain ⟨-, h | h⟩ := (hA x y).1 hadj
          · exact hne (hinj hx hy h)
          · refine hJ ?_ ?_ (Gd.ne_of_adj h) h
            · simp only [Finset.coe_image, Set.mem_image, Finset.mem_coe]; exact ⟨x, hx, rfl⟩
            · simp only [Finset.coe_image, Set.mem_image, Finset.mem_coe]; exact ⟨y, hy, rfl⟩
  3. The canonical section L(J) = {(j, 0) : j ∈ J} embeds subsets of V(G) into subsets of V(H) with |L(J)| = |J| and π(L(J)) = J.

    Because each a(i) > 0, the element 0 is available in every fiber Fin(a(i)). The assignment i ↦ (i, 0) is injective by projecting to the first component using congrArg, so L preserves cardinality by Finset.card_image_of_injective. Projecting L(J) back to the first component recovers J.

    lines 47–52

    uses congrArg, Finset.card_image_of_injective

      let L : Finset V → Finset (Σ i, Fin (a i)) := fun J => J.image (fun i => ⟨i, ⟨0, ha i⟩⟩)
      have L_inj : Function.Injective (fun i : V => (⟨i, ⟨0, ha i⟩⟩ : Σ i, Fin (a i))) := by
        intro i j h; exact congrArg Sigma.fst h
      have L_card : ∀ J, (L J).card = J.card := fun J => Finset.card_image_of_injective _ L_inj
      have L_fst : ∀ J, (L J).image Sigma.fst = J := by
        intro J; ext x; simp [L]
  4. If I is a maximal independent set in H^d, then its projection π(I) is a maximal independent set in G^d and |π(I)| = |I|.

    By injectivity of the projection on I, |π(I)| = |I| via Finset.card_image_of_injOn. If π(I) were not maximal in G^d, there would be some k ∉ π(I) independent from π(I) in G^d. Then adding z = (k, 0) to I would form a strictly larger independent set in H^d (using Finset.subset_insert and Finset.mem_insert_self), contradicting the maximality of I in H^d.

    lines 54–78

    uses Finset.card_image_of_injOn, Finset.subset_insert, Finset.mem_insert_self

      have max_proj : ∀ I, Maximal (fun u : Finset (Σ i, Fin (a i)) => Hd.IsIndepSet (u : Set (Σ i, Fin (a i)))) I →
          Maximal (fun u : Finset V => Gd.IsIndepSet (u : Set V)) (I.image Sigma.fst) ∧
            (I.image Sigma.fst).card = I.card := by
        intro I hI
        obtain ⟨hinj, hJ⟩ := (indep_iff I).1 hI.1
        refine ⟨⟨hJ, fun t ht hsub => ?_⟩, Finset.card_image_of_injOn hinj⟩
        intro k hk
        by_contra hkn
        set z : Σ i, Fin (a i) := ⟨k, ⟨0, ha k⟩⟩
        have hzI : z ∉ I := fun hz => hkn (Finset.mem_image.2 ⟨z, hz, rfl⟩)
        have hind : Hd.IsIndepSet ((insert z I : Finset (Σ i, Fin (a i))) : Set (Σ i, Fin (a i))) := by
          intro x hx y hy hne hadj
          simp only [Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hx hy
          have hnz : ∀ x ∈ I, ¬ Hd.Adj z x := by
            intro x hx h
            obtain ⟨-, h | h⟩ := (hA z x).1 h
            · exact hkn (Finset.mem_image.2 ⟨x, hx, h.symm⟩)
            · exact ht hk (hsub (Finset.mem_image.2 ⟨x, hx, rfl⟩)) (Gd.ne_of_adj h) h
          rcases hx with rfl | hx <;> rcases hy with rfl | hy
          · exact hne rfl
          · exact hnz y hy hadj
          · exact hnz x hx hadj.symm
          · exact hI.1 hx hy hne hadj
        have := hI.2 hind (Finset.subset_insert _ _)
        exact hzI (this (Finset.mem_insert_self _ _))
  5. If J is a maximal independent set in G^d, then its canonical lift L(J) is a maximal independent set in H^d.

    The lift L(J) is independent in H^d because π is injective on L(J) and π(L(J)) = J is independent in G^d. If L(J) were not maximal, some y ∉ L(J) could be added to it. If y.1 ∈ J, y is adjacent in H^d to (y.1, 0) ∈ L(J). If y.1 ∉ J, then J ∪ {y.1} would be an independent set in G^d strictly containing J (via Finset.subset_insert and Finset.mem_insert_self), contradicting maximality of J in G^d.

    lines 79–111

    uses Finset.subset_insert, Finset.mem_insert_self

      have max_lift : ∀ J, Maximal (fun u : Finset V => Gd.IsIndepSet (u : Set V)) J →
          Maximal (fun u : Finset (Σ i, Fin (a i)) => Hd.IsIndepSet (u : Set (Σ i, Fin (a i)))) (L J) := by
        intro J hJ
        have hindL : Hd.IsIndepSet ((L J : Finset (Σ i, Fin (a i))) : Set (Σ i, Fin (a i))) := by
          refine (indep_iff _).2 ⟨?_, by rw [L_fst]; exact hJ.1⟩
          intro x hx y hy hxy
          simp only [L, Finset.coe_image, Set.mem_image, Finset.mem_coe] at hx hy
          obtain ⟨i, -, rfl⟩ := hx
          obtain ⟨j, -, rfl⟩ := hy
          simp only at hxy; subst hxy; rfl
        refine ⟨hindL, fun t ht hsub => ?_⟩
        intro y hy
        by_contra hyn
        by_cases hyJ : y.1 ∈ J
        · -- y is in the same part as a member of L J
          have hmem : (⟨y.1, ⟨0, ha y.1⟩⟩ : Σ i, Fin (a i)) ∈ L J :=
            Finset.mem_image.2 ⟨y.1, hyJ, rfl⟩
          have hne : y ≠ ⟨y.1, ⟨0, ha y.1⟩⟩ := fun e => hyn (e ▸ hmem)
          exact ht hy (hsub hmem) hne ((hA _ _).2 ⟨hne, Or.inl rfl⟩)
        · have hind : Gd.IsIndepSet ((insert y.1 J : Finset V) : Set V) := by
            intro i hi j hj hij hadj
            simp only [Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hi hj
            have hny : ∀ j ∈ J, ¬ Gd.Adj y.1 j := by
              intro j hj h
              have hmem : (⟨j, ⟨0, ha j⟩⟩ : Σ i, Fin (a i)) ∈ L J := Finset.mem_image.2 ⟨j, hj, rfl⟩
              have hne : y ≠ ⟨j, ⟨0, ha j⟩⟩ := fun e => hyn (e ▸ hmem)
              exact ht hy (hsub hmem) hne ((hA _ _).2 ⟨hne, Or.inr h⟩)
            rcases hi with rfl | hi <;> rcases hj with rfl | hj
            · exact hij rfl
            · exact hny j hj hadj
            · exact hny i hi hadj.symm
            · exact hJ.1 hi hj hij hadj
          exact hyJ (hJ.2 hind (Finset.subset_insert _ _) (Finset.mem_insert_self _ _))
  6. G^d is well-covered if and only if H^d is well-covered.

    A graph is well-covered when all maximal independent sets have identical sizes. If G^d is well-covered, any two maximal independent sets I, I' in H^d project to maximal independent sets in G^d with the same sizes |I| and |I'|, so |I| = |I'|. Conversely, if H^d is well-covered, any two maximal independent sets J, J' in G^d lift to maximal independent sets in H^d of sizes |J| and |J'|, so |J| = |J'|.

    lines 112–119

      constructor
      · intro hG I I' hI hI'
        obtain ⟨h1, c1⟩ := max_proj I hI
        obtain ⟨h2, c2⟩ := max_proj I' hI'
        rw [← c1, ← c2]; exact hG _ _ h1 h2
      · intro hH J J' hJ hJ'
        rw [← L_card J, ← L_card J']
        exact hH _ _ (max_lift J hJ) (max_lift J' hJ')
simple_graph_clique_blowup_edist
For two vertices in the clique blowup whose projections to the base graph are distinct, their distance in the clique blowup equals the distance between their projections in the base graph.
simple_graph_clique_blowup_power_adj_iff
Two vertices in the clique blowup are adjacent in its d-th graph power if and only if they are distinct and either have the same projection or their projections are adjacent in the d-th power of the base graph.
congrArg
Equal inputs produce equal outputs under any function.
Finset.card_image_of_injective
An injective map between finite sets preserves the cardinality of the set under its image.
Finset.card_image_of_injOn
A map injective on a finite set preserves the set's cardinality under its image.
Finset.subset_insert
A set is a subset of the result of inserting an element into it.
Finset.mem_insert_self
An element belongs to the set obtained by inserting that element into any set.

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

theorem simple_graph_clique_blowup_power_adj_iff {V : Type*} (G : SimpleGraph V) (a : V → ℕ)    (ha : ∀ i, 0 < a i) (d : ℕ) (hd : 1 ≤ d) (p q : Σ i, Fin (a i)) :    (simple_graph_power (simple_graph_clique_blowup G a) d).Adj p q ↔      p ≠ q ∧ (p.1 = q.1 ∨ (simple_graph_power G d).Adj p.1 q.1) := by  simp only [simple_graph_power]  constructor  · rintro ⟨hne, hle⟩    refine ⟨hne, ?_⟩    by_cases h : p.1 = q.1    · exact Or.inl h    · right; exact ⟨h, by rwa [← simple_graph_clique_blowup_edist G a ha p q h]⟩  · rintro ⟨hne, h | ⟨h1, h2⟩⟩    · refine ⟨hne, ?_⟩      have hadj : (simple_graph_clique_blowup G a).Adj p q := Or.inl ⟨h, hne⟩      rw [SimpleGraph.edist_eq_one_iff_adj.2 hadj]; exact_mod_cast hd    · exact ⟨hne, by rwa [simple_graph_clique_blowup_edist G a ha p q h1]⟩theorem simple_graph_power_well_covered_iff_clique_blowup {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (a : V → ℕ) (ha : ∀ i, 0 < a i) (d : ℕ) (hd : 1 ≤ d) :    simple_graph_is_well_covered (simple_graph_power G d) ↔      simple_graph_is_well_covered (simple_graph_power (simple_graph_clique_blowup G a) d) := by  set Gd := simple_graph_power G d  set Hd := simple_graph_power (simple_graph_clique_blowup G a) d  have hA := simple_graph_clique_blowup_power_adj_iff G a ha d hd  -- independence in Hd  have indep_iff : ∀ I : Finset (Σ i, Fin (a i)), Hd.IsIndepSet (I : Set (Σ i, Fin (a i))) ↔      (Set.InjOn (Sigma.fst : (Σ i, Fin (a i)) → V) (I : Set (Σ i, Fin (a i))) ∧ Gd.IsIndepSet ((I.image Sigma.fst : Finset V) : Set V)) := by    intro I    constructor    · intro hI      refine ⟨fun x hx y hy hxy => ?_, ?_⟩      · by_contra hne        exact hI hx hy hne ((hA x y).2 ⟨hne, Or.inl hxy⟩)      · intro i hi j hj hij hadj        simp only [Finset.coe_image, Set.mem_image, Finset.mem_coe] at hi hj        obtain ⟨x, hx, rfl⟩ := hi        obtain ⟨y, hy, rfl⟩ := hj        have hne : x ≠ y := fun e => hij (e ▸ rfl)        exact hI hx hy hne ((hA x y).2 ⟨hne, Or.inr hadj⟩)    · rintro ⟨hinj, hJ⟩ x hx y hy hne hadj      obtain ⟨-, h | h⟩ := (hA x y).1 hadj      · exact hne (hinj hx hy h)      · refine hJ ?_ ?_ (Gd.ne_of_adj h) h        · simp only [Finset.coe_image, Set.mem_image, Finset.mem_coe]; exact ⟨x, hx, rfl⟩        · simp only [Finset.coe_image, Set.mem_image, Finset.mem_coe]; exact ⟨y, hy, rfl⟩  -- lift of a set of parts  let L : Finset V → Finset (Σ i, Fin (a i)) := fun J => J.image (fun i => ⟨i, ⟨0, ha i⟩⟩)  have L_inj : Function.Injective (fun i : V => (⟨i, ⟨0, ha i⟩⟩ : Σ i, Fin (a i))) := by    intro i j h; exact congrArg Sigma.fst h  have L_card : ∀ J, (L J).card = J.card := fun J => Finset.card_image_of_injective _ L_inj  have L_fst : ∀ J, (L J).image Sigma.fst = J := by    intro J; ext x; simp [L]  -- maximal independent sets correspond  have max_proj : ∀ I, Maximal (fun u : Finset (Σ i, Fin (a i)) => Hd.IsIndepSet (u : Set (Σ i, Fin (a i)))) I →      Maximal (fun u : Finset V => Gd.IsIndepSet (u : Set V)) (I.image Sigma.fst) ∧        (I.image Sigma.fst).card = I.card := by    intro I hI    obtain ⟨hinj, hJ⟩ := (indep_iff I).1 hI.1    refine ⟨⟨hJ, fun t ht hsub => ?_⟩, Finset.card_image_of_injOn hinj⟩    intro k hk    by_contra hkn    set z : Σ i, Fin (a i) := ⟨k, ⟨0, ha k⟩⟩    have hzI : z ∉ I := fun hz => hkn (Finset.mem_image.2 ⟨z, hz, rfl⟩)    have hind : Hd.IsIndepSet ((insert z I : Finset (Σ i, Fin (a i))) : Set (Σ i, Fin (a i))) := by      intro x hx y hy hne hadj      simp only [Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hx hy      have hnz : ∀ x ∈ I, ¬ Hd.Adj z x := by        intro x hx h        obtain ⟨-, h | h⟩ := (hA z x).1 h        · exact hkn (Finset.mem_image.2 ⟨x, hx, h.symm⟩)        · exact ht hk (hsub (Finset.mem_image.2 ⟨x, hx, rfl⟩)) (Gd.ne_of_adj h) h      rcases hx with rfl | hx <;> rcases hy with rfl | hy      · exact hne rfl      · exact hnz y hy hadj      · exact hnz x hx hadj.symm      · exact hI.1 hx hy hne hadj    have := hI.2 hind (Finset.subset_insert _ _)    exact hzI (this (Finset.mem_insert_self _ _))  have max_lift : ∀ J, Maximal (fun u : Finset V => Gd.IsIndepSet (u : Set V)) J →      Maximal (fun u : Finset (Σ i, Fin (a i)) => Hd.IsIndepSet (u : Set (Σ i, Fin (a i)))) (L J) := by    intro J hJ    have hindL : Hd.IsIndepSet ((L J : Finset (Σ i, Fin (a i))) : Set (Σ i, Fin (a i))) := by      refine (indep_iff _).2 ⟨?_, by rw [L_fst]; exact hJ.1⟩      intro x hx y hy hxy      simp only [L, Finset.coe_image, Set.mem_image, Finset.mem_coe] at hx hy      obtain ⟨i, -, rfl⟩ := hx      obtain ⟨j, -, rfl⟩ := hy      simp only at hxy; subst hxy; rfl    refine ⟨hindL, fun t ht hsub => ?_⟩    intro y hy    by_contra hyn    by_cases hyJ : y.1 ∈ J    · -- y is in the same part as a member of L J      have hmem : (⟨y.1, ⟨0, ha y.1⟩⟩ : Σ i, Fin (a i)) ∈ L J :=        Finset.mem_image.2 ⟨y.1, hyJ, rfl⟩      have hne : y ≠ ⟨y.1, ⟨0, ha y.1⟩⟩ := fun e => hyn (e ▸ hmem)      exact ht hy (hsub hmem) hne ((hA _ _).2 ⟨hne, Or.inl rfl⟩)    · have hind : Gd.IsIndepSet ((insert y.1 J : Finset V) : Set V) := by        intro i hi j hj hij hadj        simp only [Finset.coe_insert, Set.mem_insert_iff, Finset.mem_coe] at hi hj        have hny : ∀ j ∈ J, ¬ Gd.Adj y.1 j := by          intro j hj h          have hmem : (⟨j, ⟨0, ha j⟩⟩ : Σ i, Fin (a i)) ∈ L J := Finset.mem_image.2 ⟨j, hj, rfl⟩          have hne : y ≠ ⟨j, ⟨0, ha j⟩⟩ := fun e => hyn (e ▸ hmem)          exact ht hy (hsub hmem) hne ((hA _ _).2 ⟨hne, Or.inr h⟩)        rcases hi with rfl | hi <;> rcases hj with rfl | hj        · exact hij rfl        · exact hny j hj hadj        · exact hny i hi hadj.symm        · exact hJ.1 hi hj hij hadj      exact hyJ (hJ.2 hind (Finset.subset_insert _ _) (Finset.mem_insert_self _ _))  constructor  · intro hG I I' hI hI'    obtain ⟨h1, c1⟩ := max_proj I hI    obtain ⟨h2, c2⟩ := max_proj I' hI'    rw [← c1, ← c2]; exact hG _ _ h1 h2  · intro hH J J' hJ hJ'    rw [← L_card J, ← L_card J']    exact hH _ _ (max_lift J hJ) (max_lift J' hJ')
See it in the graphDiscuss this resultChallenge it