simple_graph_power_well_covered_iff_clique_blowup
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
- forall_power_well_covered_iff_clique_blowupLet 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…
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.
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.
uses
simple_graph_clique_blowup_edistsimp 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]⟩
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.
uses
simple_graph_clique_blowup_power_adj_iffset 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⟩
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.
uses
congrArg,Finset.card_image_of_injectivelet 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]
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.
uses
Finset.card_image_of_injOn,Finset.subset_insert,Finset.mem_insert_selfhave 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 _ _))
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.
uses
Finset.subset_insert,Finset.mem_insert_selfhave 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 _ _))
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'|.
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
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 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')