boxProd_completeGraph_all_powers_well_covered
Let G be a finite connected nontrivial graph, and let t be an integer with t > |V(G)|. If every positive power G^d (d ≥ 1) is well-covered, then every positive power of the Cartesian product G □ K_t is well-covered.
Statement
theorem boxProd_completeGraph_all_powers_well_covered {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hnontriv : 2 ≤ Fintype.card V) (hwc : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) (t : ℕ) (ht : Fintype.card V < t) : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d)
- Formalizes
- arXiv:2611.03956 Theorem 2.11 (1)
- Verified
- 05 Nov 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…
- OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
- 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_is_well_covered_botThe edgeless graph on a finite vertex set is well-covered (its only maximal independent set is the whole vertex set).
- Used by 1
- exists_connected_all_powers_well_covered_diam_geFor every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d…
Read back from the Lean
Let $V$ be a finite type and let $G$ be a simple graph on $V$.
Assume:
1. $G$ is connected (G.Connected);
2. $V$ has at least 2 vertices (2 ≤ Fintype.card V);
3. For every natural number $d \ge 1$, the $d$-th power of $G$ is well-covered;
4. $t$ is a natural number strictly greater than the cardinality of $V$ (Fintype.card V < t).
Then, for every natural number $d \ge 1$, the $d$-th power of the Cartesian product (box product) of $G$ with the complete graph on Fin t (that is, $G \mathbin{\square} K_t$) 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 prove that every power (G □ K_t)^d is well-covered for d ≥ 1, the argument shows that the projection map (u, i) ↦ u sets up a size-preserving correspondence between maximal independent sets of (G □ K_t)^d and maximal independent sets of G^(d - 1). The projection is injective on any independent set because distinct vertices with the same G-coordinate are adjacent in K_t and thus at distance 1 ≤ d in the product. The projection of a maximal independent set s is maximal in G^(d - 1) because the hypothesis t > |V(G)| ensures that any vertex outside the projection at distance ≥ d from all elements of s could be paired with an unused coordinate in K_t to enlarge s, contradicting maximality. Since G^(d - 1) is well-covered, all maximal independent sets in G^(d - 1) have equal cardinality, which implies that all maximal independent sets of (G □ K_t)^d also have equal cardinality.
The 0-th power graph G⁰ is the empty graph ⊥.
An edge in G⁰ connects distinct vertices u ≠ v at distance ≤ 0. But distance ≤ 0 implies distance 0, which forces u = v by SimpleGraph.edist_eq_zero_iff.mp, a contradiction. Thus G⁰ has no edges.
uses
simple_graph_power,SimpleGraph.bot_adj,le_antisymm,bot_le,SimpleGraph.edist_eq_zero_iff.mpclassical have hpow0 : simple_graph_power G 0 = ⊥ := by ext u v simp only [simple_graph_power, SimpleGraph.bot_adj] constructor · intro h have hz : G.edist u v = 0 := le_antisymm (by simpa using h.2) bot_le exact h.1 (SimpleGraph.edist_eq_zero_iff.mp hz) · intro h; exact h.elim
The projection map (u, i) ↦ u is injective on any independent set of (G □ K_t)^d.
If two distinct elements (u, i) and (v, j) in an independent set s have the same first coordinate u = v, they must differ in their second coordinate i ≠ j. In the Cartesian product G □ K_t, their distance is edist_G(u, u) + edist_{K_t}(i, j) = 0 + 1 = 1. Since d ≥ 1, this distance is at most d, so the two vertices are adjacent in (G □ K_t)^d, contradicting independence of s.
uses
SimpleGraph.isIndepSet_iff,Prod.ext,SimpleGraph.edist_boxProd,SimpleGraph.edist_self,SimpleGraph.completeGraph_eq_top,SimpleGraph.edist_top,zero_addhave hinj : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((s : Set (V × Fin t))) → Set.InjOn Prod.fst ((s : Set (V × Fin t))) := by intro d s hd h rw [SimpleGraph.isIndepSet_iff] at h intro p hp q hq hpq by_contra hne have hpair := h hp hq hne apply hpair have hd2 : p.2 ≠ q.2 := by intro hc exact hne (Prod.ext hpq hc) refine ⟨hne, ?_⟩ show (G □ SimpleGraph.completeGraph (Fin t)).edist p q ≤ (d : ℕ∞) rw [SimpleGraph.edist_boxProd] have h1 : G.edist p.1 q.1 = 0 := by rw [hpq]; exact SimpleGraph.edist_self rw [h1] have hk : (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 ≤ 1 := by rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top] split <;> simp calc (0 : ℕ∞) + (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 = (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 := zero_add _ _ ≤ 1 := hk _ ≤ (d : ℕ∞) := by exact_mod_cast hd
Any independent set of (G □ K_t)^d has the same cardinality as its projection onto V.
Because the projection onto the first component is injective on the independent set s (as established in the previous step), Finset.card_image_of_injOn proves that |π₁(s)| = |s|.
uses
Finset.card_image_of_injOnhave hcard : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((s : Set (V × Fin t))) → (s.image Prod.fst).card = s.card := by intro d s hd h exact Finset.card_image_of_injOn (hinj d s hd h)
Every vertex outside the projection of a maximal independent set is within distance d - 1 of some vertex in the projection.
Suppose for contradiction that some vertex v ∉ π₁(s) has distance > d - 1 (hence ≥ d) to every w ∈ π₁(s). A choice of index i ∈ Fin t would create an adjacency between (v, i) and some (w, j) ∈ s in (G □ K_t)^d only if edist_G(v, w) + edist_{K_t}(i, j) ≤ d, which can happen only when edist_G(v, w) = d and i = j. The set of such "bad" indices has cardinality at most |s| = |π₁(s)| ≤ |V(G)| < t. Because t > |V(G)|, there exists an index i that is not bad. Then (v, i) has distance > d to every vertex of s, so s ∪ {(v, i)} remains independent, contradicting the maximality of s.
uses
Finset.card_le_univ,Finset.card_image_le,Finset.card_filter_le,Order.add_one_le_of_lt,SimpleGraph.edist_boxProd,SimpleGraph.completeGraph_eq_top,SimpleGraph.edist_top,SimpleGraph.isIndepSet_iff,Set.pairwise_inserthave hdom : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → Maximal (fun u : Finset (V × Fin t) => (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet (↑u)) s → ∀ v : V, v ∉ s.image Prod.fst → ∃ w ∈ s.image Prod.fst, G.edist v w ≤ ((d - 1 : ℕ) : ℕ∞) := by intro d s hd hs v hv by_contra hcon push_neg at hcon have hscard_eq : (s.image Prod.fst).card = s.card := hcard d s hd hs.1 have hscard_le : s.card ≤ Fintype.card V := by rw [← hscard_eq]; exact Finset.card_le_univ _ set bad : Finset (Fin t) := (s.filter (fun p => G.edist v p.1 = (d : ℕ∞))).image Prod.snd with hbad_def have hbad_card : bad.card ≤ s.card := by rw [hbad_def] exact le_trans Finset.card_image_le (Finset.card_filter_le _ _) have hbad_lt : bad.card < t := lt_of_le_of_lt (le_trans hbad_card hscard_le) ht have hex : ∃ i : Fin t, i ∉ bad := by by_contra hc push_neg at hc have huniv : bad = Finset.univ := Finset.eq_univ_iff_forall.2 hc rw [huniv] at hbad_lt simp at hbad_lt obtain ⟨i, hi⟩ := hex have hnonadj : ∀ b ∈ s, ¬ (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).Adj (v, i) b := by intro b hb hadj obtain ⟨w, j⟩ := b have hw : w ∈ s.image Prod.fst := Finset.mem_image.2 ⟨(w, j), hb, rfl⟩ have hlt : ((d - 1 : ℕ) : ℕ∞) < G.edist v w := hcon w hw have hdle : (d : ℕ∞) ≤ G.edist v w := by have hadd : ((d - 1 : ℕ) : ℕ∞) + 1 ≤ G.edist v w := Order.add_one_le_of_lt hlt have harith : ((d - 1 : ℕ) : ℕ∞) + 1 = (d : ℕ∞) := by have hh : (d - 1 : ℕ) + 1 = d := Nat.sub_add_cancel hd rw [← hh]; push_cast; ring rwa [harith] at hadd have hHlt : (d : ℕ∞) < (G □ SimpleGraph.completeGraph (Fin t)).edist (v, i) (w, j) := by rw [SimpleGraph.edist_boxProd] by_cases heq : G.edist v w = (d : ℕ∞) · have hmem : (w, j) ∈ s.filter (fun p => G.edist v p.1 = (d : ℕ∞)) := Finset.mem_filter.2 ⟨hb, heq⟩ have hj : j ∈ bad := by rw [hbad_def]; exact Finset.mem_image.2 ⟨(w,j), hmem, rfl⟩ have hij : i ≠ j := fun h => hi (h ▸ hj) have hK : (SimpleGraph.completeGraph (Fin t)).edist i j = 1 := by rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top]; simp [hij] rw [heq, hK] have harith : (d:ℕ∞) + 1 = ((d+1 : ℕ) : ℕ∞) := by rw [← Nat.cast_one, ← Nat.cast_add] rw [harith] exact_mod_cast Nat.lt_succ_self d · have hgrad : (d : ℕ∞) < G.edist v w := lt_of_le_of_ne hdle (Ne.symm heq) exact lt_of_lt_of_le hgrad (le_add_right (le_refl _)) exact absurd hadj.2 (not_le.mpr hHlt) have hIns : (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((insert (v, i) s : Finset (V × Fin t)) : Set (V × Fin t)) := by rw [Finset.coe_insert, SimpleGraph.isIndepSet_iff, Set.pairwise_insert] refine ⟨(SimpleGraph.isIndepSet_iff _).1 hs.1, ?_⟩ intro b hb hne exact ⟨hnonadj b hb, fun hba => hnonadj b hb hba.symm⟩ have hsub : s ≤ insert (v, i) s := Finset.subset_insert _ _ have hle := hs.2 hIns hsub have hmem : (v, i) ∈ s := hle (Finset.mem_insert_self _ _) exact hv (Finset.mem_image.2 ⟨(v, i), hmem, rfl⟩)
The projection of any maximal independent set of (G □ K_t)^d is a maximal independent set of G^(d - 1).
First, π₁(s) is independent in G^(d - 1): if distinct vertices v, w ∈ π₁(s) were adjacent, their distance in G would be ≤ d - 1, which would imply their preimages in s have product distance ≤ (d - 1) + 1 = d, contradicting the independence of s in (G □ K_t)^d. Second, π₁(s) is maximal: any vertex v ∉ π₁(s) is within distance ≤ d - 1 of some w ∈ π₁(s) by the domination property proved in the previous step, so v is adjacent to w in G^(d - 1) and cannot be added.
uses
SimpleGraph.isIndepSet_iff,Finset.coe_image,SimpleGraph.completeGraph_eq_top,SimpleGraph.edist_top,SimpleGraph.edist_boxProd,add_le_addhave hpm : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → Maximal (fun u : Finset (V × Fin t) => (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet (↑u)) s → Maximal (fun u : Finset V => (simple_graph_power G (d - 1)).IsIndepSet (↑u)) (s.image Prod.fst) := by intro d s hd hs have hindep : (simple_graph_power G (d - 1)).IsIndepSet ((s.image Prod.fst : Finset V) : Set V) := by rw [SimpleGraph.isIndepSet_iff] intro v hv w hw hvw rw [Finset.coe_image] at hv hw obtain ⟨p, hp, rfl⟩ := hv obtain ⟨q, hq, hwq⟩ := hw rw [← hwq] at hvw ⊢ intro hadj have hpq_ne : p ≠ q := by intro hpq; exact hvw (by rw [hpq]) have hsind : (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((s : Set (V × Fin t))) := hs.1 rw [SimpleGraph.isIndepSet_iff] at hsind have hnonadj : ¬ (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).Adj p q := hsind hp hq hpq_ne have hlt : (d : ℕ∞) < (G □ SimpleGraph.completeGraph (Fin t)).edist p q := by by_contra hc; exact hnonadj ⟨hpq_ne, not_lt.mp hc⟩ have hadj' : G.edist p.1 q.1 ≤ ((d - 1 : ℕ) : ℕ∞) := hadj.2 have hk : (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 ≤ 1 := by rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top]; split <;> simp have hbound : (G □ SimpleGraph.completeGraph (Fin t)).edist p q ≤ (d : ℕ∞) := by rw [SimpleGraph.edist_boxProd] calc G.edist p.1 q.1 + (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 ≤ ((d - 1 : ℕ) : ℕ∞) + 1 := add_le_add hadj' hk _ = (d : ℕ∞) := by have h : (d - 1 : ℕ) + 1 = d := Nat.sub_add_cancel hd rw [← h]; push_cast; ring exact absurd hbound (not_le.mpr hlt) refine ⟨hindep, ?_⟩ intro D' hD' hsub v hvD' by_contra hv obtain ⟨w, hw, hed⟩ := hdom d s hd hs v hv have hwD' : w ∈ D' := hsub hw have hvw : v ≠ w := fun h => hv (h ▸ hw) rw [SimpleGraph.isIndepSet_iff] at hD' exact (hD' hvD' hwD' hvw) ⟨hvw, hed⟩
All powers G^e (for e ≥ 0) are well-covered.
When e = 0, G⁰ = ⊥ is well-covered by simple_graph_is_well_covered_bot. When e ≥ 1, this is given directly by the theorem assumption hwc.
uses
Nat.eq_zero_or_pos,simple_graph_is_well_covered_bothave hAllPow : ∀ e : ℕ, simple_graph_is_well_covered (simple_graph_power G e) := by intro e rcases Nat.eq_zero_or_pos e with he | he · rw [he, hpow0] exact simple_graph_is_well_covered_bot · exact hwc e he
Every positive power of G □ K_t is well-covered.
Given d ≥ 1 and any two maximal independent sets s and t of (G □ K_t)^d, their projections π₁(s) and π₁(t) are maximal independent sets of G^(d - 1). Since G^(d - 1) is well-covered, |π₁(s)| = |π₁(t)|. Since projection preserves size (|s| = |π₁(s)| and |t| = |π₁(t)|), it follows that |s| = |t|.
intro d hd s t hs ht have hps := hpm d s hd hs have hpt := hpm d t hd ht have hD := hAllPow (d - 1) (s.image Prod.fst) (t.image Prod.fst) hps hpt have hcs := hcard d s hd hs.1 have hct := hcard d t hd ht.1 omega
simple_graph_power- The d-th power of a graph G has an edge between two distinct vertices if and only if their distance in G is at most d.
SimpleGraph.bot_adj- The empty graph ⊥ has no edges between any pair of vertices.
le_antisymm- In a partial order, if a ≤ b and b ≤ a, then a = b.
bot_le- The bottom element ⊥ is less than or equal to every element in a bounded order.
SimpleGraph.edist_eq_zero_iff.mp- If the distance between two vertices in a graph is zero, the vertices are identical.
SimpleGraph.isIndepSet_iff- A set of vertices is independent if and only if no two distinct vertices in the set are adjacent.
Prod.ext- Two ordered pairs are equal if and only if their first components and second components are respectively equal.
SimpleGraph.edist_boxProd- The distance between two vertices in a Cartesian product graph is the sum of the distances in the factor graphs.
SimpleGraph.edist_self- The distance from any vertex to itself is 0.
SimpleGraph.completeGraph_eq_top- The complete graph on a vertex set is the top graph ⊤ with all possible edges.
SimpleGraph.edist_top- In a complete graph, the distance between distinct vertices is 1 and between identical vertices is 0.
zero_add- Adding zero to an element leaves it unchanged.
Finset.card_image_of_injOn- If a function is injective on a finite set, the image has the same cardinality as the domain set.
Finset.card_le_univ- The cardinality of any subset of a finite type is at most the total number of elements in the type.
Finset.card_image_le- The cardinality of the image of a finite set is at most the cardinality of the original set.
Finset.card_filter_le- Filtering a finite set by a predicate yields a subset of cardinality at most that of the original set.
Order.add_one_le_of_lt- In a discrete order, if x < y, then x + 1 ≤ y.
Set.pairwise_insert- A relation holds pairwise on s ∪ {a} if and only if it holds on s and holds between a and every distinct element of s.
Finset.coe_image- The set coercion of the image of a Finset equals the image of the coerced set.
add_le_add- If a ≤ b and c ≤ d, then a + c ≤ b + d.
Nat.eq_zero_or_pos- Every natural number is either zero or strictly positive.
simple_graph_is_well_covered_bot- The empty graph ⊥ is well-covered.
- In the formal proof, the 0-th power graph G⁰ is defined and shown to be the empty graph ⊥ (which is well-covered), allowing the case d = 1 to be treated uniformly with d ≥ 2 by considering G^(d - 1).
- In the final step (lines 149–155), the variable name `t` introduced for the second maximal independent set shadows the theorem parameter `t : ℕ`.
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.
/-- If G has well-covered powers and t > |V(G)|, then G □ K_t has well-covered powers. -/theorem boxProd_completeGraph_all_powers_well_covered {V : Type*} [Fintype V] (G : SimpleGraph V) (hconn : G.Connected) (hnontriv : 2 ≤ Fintype.card V) (hwc : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) (t : ℕ) (ht : Fintype.card V < t) : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d) := by classical have hpow0 : simple_graph_power G 0 = ⊥ := by ext u v simp only [simple_graph_power, SimpleGraph.bot_adj] constructor · intro h have hz : G.edist u v = 0 := le_antisymm (by simpa using h.2) bot_le exact h.1 (SimpleGraph.edist_eq_zero_iff.mp hz) · intro h; exact h.elim have hinj : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((s : Set (V × Fin t))) → Set.InjOn Prod.fst ((s : Set (V × Fin t))) := by intro d s hd h rw [SimpleGraph.isIndepSet_iff] at h intro p hp q hq hpq by_contra hne have hpair := h hp hq hne apply hpair have hd2 : p.2 ≠ q.2 := by intro hc exact hne (Prod.ext hpq hc) refine ⟨hne, ?_⟩ show (G □ SimpleGraph.completeGraph (Fin t)).edist p q ≤ (d : ℕ∞) rw [SimpleGraph.edist_boxProd] have h1 : G.edist p.1 q.1 = 0 := by rw [hpq]; exact SimpleGraph.edist_self rw [h1] have hk : (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 ≤ 1 := by rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top] split <;> simp calc (0 : ℕ∞) + (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 = (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 := zero_add _ _ ≤ 1 := hk _ ≤ (d : ℕ∞) := by exact_mod_cast hd have hcard : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((s : Set (V × Fin t))) → (s.image Prod.fst).card = s.card := by intro d s hd h exact Finset.card_image_of_injOn (hinj d s hd h) have hdom : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → Maximal (fun u : Finset (V × Fin t) => (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet (↑u)) s → ∀ v : V, v ∉ s.image Prod.fst → ∃ w ∈ s.image Prod.fst, G.edist v w ≤ ((d - 1 : ℕ) : ℕ∞) := by intro d s hd hs v hv by_contra hcon push_neg at hcon have hscard_eq : (s.image Prod.fst).card = s.card := hcard d s hd hs.1 have hscard_le : s.card ≤ Fintype.card V := by rw [← hscard_eq]; exact Finset.card_le_univ _ set bad : Finset (Fin t) := (s.filter (fun p => G.edist v p.1 = (d : ℕ∞))).image Prod.snd with hbad_def have hbad_card : bad.card ≤ s.card := by rw [hbad_def] exact le_trans Finset.card_image_le (Finset.card_filter_le _ _) have hbad_lt : bad.card < t := lt_of_le_of_lt (le_trans hbad_card hscard_le) ht have hex : ∃ i : Fin t, i ∉ bad := by by_contra hc push_neg at hc have huniv : bad = Finset.univ := Finset.eq_univ_iff_forall.2 hc rw [huniv] at hbad_lt simp at hbad_lt obtain ⟨i, hi⟩ := hex have hnonadj : ∀ b ∈ s, ¬ (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).Adj (v, i) b := by intro b hb hadj obtain ⟨w, j⟩ := b have hw : w ∈ s.image Prod.fst := Finset.mem_image.2 ⟨(w, j), hb, rfl⟩ have hlt : ((d - 1 : ℕ) : ℕ∞) < G.edist v w := hcon w hw have hdle : (d : ℕ∞) ≤ G.edist v w := by have hadd : ((d - 1 : ℕ) : ℕ∞) + 1 ≤ G.edist v w := Order.add_one_le_of_lt hlt have harith : ((d - 1 : ℕ) : ℕ∞) + 1 = (d : ℕ∞) := by have hh : (d - 1 : ℕ) + 1 = d := Nat.sub_add_cancel hd rw [← hh]; push_cast; ring rwa [harith] at hadd have hHlt : (d : ℕ∞) < (G □ SimpleGraph.completeGraph (Fin t)).edist (v, i) (w, j) := by rw [SimpleGraph.edist_boxProd] by_cases heq : G.edist v w = (d : ℕ∞) · have hmem : (w, j) ∈ s.filter (fun p => G.edist v p.1 = (d : ℕ∞)) := Finset.mem_filter.2 ⟨hb, heq⟩ have hj : j ∈ bad := by rw [hbad_def]; exact Finset.mem_image.2 ⟨(w,j), hmem, rfl⟩ have hij : i ≠ j := fun h => hi (h ▸ hj) have hK : (SimpleGraph.completeGraph (Fin t)).edist i j = 1 := by rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top]; simp [hij] rw [heq, hK] have harith : (d:ℕ∞) + 1 = ((d+1 : ℕ) : ℕ∞) := by rw [← Nat.cast_one, ← Nat.cast_add] rw [harith] exact_mod_cast Nat.lt_succ_self d · have hgrad : (d : ℕ∞) < G.edist v w := lt_of_le_of_ne hdle (Ne.symm heq) exact lt_of_lt_of_le hgrad (le_add_right (le_refl _)) exact absurd hadj.2 (not_le.mpr hHlt) have hIns : (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((insert (v, i) s : Finset (V × Fin t)) : Set (V × Fin t)) := by rw [Finset.coe_insert, SimpleGraph.isIndepSet_iff, Set.pairwise_insert] refine ⟨(SimpleGraph.isIndepSet_iff _).1 hs.1, ?_⟩ intro b hb hne exact ⟨hnonadj b hb, fun hba => hnonadj b hb hba.symm⟩ have hsub : s ≤ insert (v, i) s := Finset.subset_insert _ _ have hle := hs.2 hIns hsub have hmem : (v, i) ∈ s := hle (Finset.mem_insert_self _ _) exact hv (Finset.mem_image.2 ⟨(v, i), hmem, rfl⟩) have hpm : ∀ (d : ℕ) (s : Finset (V × Fin t)), 1 ≤ d → Maximal (fun u : Finset (V × Fin t) => (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet (↑u)) s → Maximal (fun u : Finset V => (simple_graph_power G (d - 1)).IsIndepSet (↑u)) (s.image Prod.fst) := by intro d s hd hs have hindep : (simple_graph_power G (d - 1)).IsIndepSet ((s.image Prod.fst : Finset V) : Set V) := by rw [SimpleGraph.isIndepSet_iff] intro v hv w hw hvw rw [Finset.coe_image] at hv hw obtain ⟨p, hp, rfl⟩ := hv obtain ⟨q, hq, hwq⟩ := hw rw [← hwq] at hvw ⊢ intro hadj have hpq_ne : p ≠ q := by intro hpq; exact hvw (by rw [hpq]) have hsind : (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).IsIndepSet ((s : Set (V × Fin t))) := hs.1 rw [SimpleGraph.isIndepSet_iff] at hsind have hnonadj : ¬ (simple_graph_power (G □ SimpleGraph.completeGraph (Fin t)) d).Adj p q := hsind hp hq hpq_ne have hlt : (d : ℕ∞) < (G □ SimpleGraph.completeGraph (Fin t)).edist p q := by by_contra hc; exact hnonadj ⟨hpq_ne, not_lt.mp hc⟩ have hadj' : G.edist p.1 q.1 ≤ ((d - 1 : ℕ) : ℕ∞) := hadj.2 have hk : (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 ≤ 1 := by rw [SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top]; split <;> simp have hbound : (G □ SimpleGraph.completeGraph (Fin t)).edist p q ≤ (d : ℕ∞) := by rw [SimpleGraph.edist_boxProd] calc G.edist p.1 q.1 + (SimpleGraph.completeGraph (Fin t)).edist p.2 q.2 ≤ ((d - 1 : ℕ) : ℕ∞) + 1 := add_le_add hadj' hk _ = (d : ℕ∞) := by have h : (d - 1 : ℕ) + 1 = d := Nat.sub_add_cancel hd rw [← h]; push_cast; ring exact absurd hbound (not_le.mpr hlt) refine ⟨hindep, ?_⟩ intro D' hD' hsub v hvD' by_contra hv obtain ⟨w, hw, hed⟩ := hdom d s hd hs v hv have hwD' : w ∈ D' := hsub hw have hvw : v ≠ w := fun h => hv (h ▸ hw) rw [SimpleGraph.isIndepSet_iff] at hD' exact (hD' hvD' hwD' hvw) ⟨hvw, hed⟩ have hAllPow : ∀ e : ℕ, simple_graph_is_well_covered (simple_graph_power G e) := by intro e rcases Nat.eq_zero_or_pos e with he | he · rw [he, hpow0] exact simple_graph_is_well_covered_bot · exact hwc e he intro d hd s t hs ht have hps := hpm d s hd hs have hpt := hpm d t hd ht have hD := hAllPow (d - 1) (s.image Prod.fst) (t.image Prod.fst) hps hpt have hcs := hcard d s hd hs.1 have hct := hcard d t hd ht.1 omega