AFTD Auto-Formalizing Theoretical Domains

boxProd_completeGraph_all_powers_well_covered

theoremverifiedformalization

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

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.

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

    lines 8–16

    uses simple_graph_power, SimpleGraph.bot_adj, le_antisymm, bot_le, SimpleGraph.edist_eq_zero_iff.mp

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

    lines 17–40

    uses SimpleGraph.isIndepSet_iff, Prod.ext, SimpleGraph.edist_boxProd, SimpleGraph.edist_self, SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top, zero_add

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

    lines 41–45

    uses Finset.card_image_of_injOn

      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)
  4. 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.

    lines 46–105

    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_insert

      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⟩)
  5. 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.

    lines 106–142

    uses SimpleGraph.isIndepSet_iff, Finset.coe_image, SimpleGraph.completeGraph_eq_top, SimpleGraph.edist_top, SimpleGraph.edist_boxProd, add_le_add

      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⟩
  6. 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.

    lines 143–148

    uses Nat.eq_zero_or_pos, simple_graph_is_well_covered_bot

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

    lines 149–155

      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.

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

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