AFTD Auto-Formalizing Theoretical Domains

complete_bipartite_two_two_all_powers_well_covered

theoremverifiedformalization

For every positive integer d, the d-th power of the complete bipartite graph K_{2,2} is well-covered.

Statement

theorem complete_bipartite_two_two_all_powers_well_covered :
    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (completeBipartiteGraph (Fin 2) (Fin 2)) d)
Formalizes
Deniz 2022; arXiv:2610.09300 Theorem 1.3
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…

Read back from the Lean

For every natural number $d$ with $1 \le d$, the $d$-th graph power of the complete bipartite graph $K_{2,2}$ (with parts indexed by Fin 2 and Fin 2, on vertex type Fin 2 ⊕ Fin 2) is well-covered; that is, every two maximal independent sets of vertices in this power graph have the same cardinality.

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

A graph is well-covered if all its maximal independent sets have the same cardinality. For any integer d ≥ 1, the proof splits into two cases: d = 1 and d ≥ 2. When d = 1, the power graph K_{2,2}^1 is K_{2,2} itself, whose only maximal independent sets are its two bipartite parts (each of size 2). When d ≥ 2, the diameter of K_{2,2} is at most 2, so every pair of distinct vertices is at distance at most d, making K_{2,2}^d the complete graph ⊤, in which all maximal independent sets are singletons of size 1.

  1. The left partition class of K_{2,2} has cardinality 2.

    The left set is defined as the image of Finset.univ on Fin 2 under the injection Sum.inl. Since Sum.inl is injective, the cardinality of the image equals that of Fin 2, which is 2.

    lines 14–17

    uses Finset.card_image_of_injective, Sum.inl_injective

      rw [complete_bipartite_two_two_all_powers_well_covered_leftSet,
          Finset.card_image_of_injective _ Sum.inl_injective]
      simp
    
  2. The right partition class of K_{2,2} has cardinality 2.

    Similarly, the right set is the image of Finset.univ on Fin 2 under the injection Sum.inr, so its cardinality is also 2.

    lines 20–23

    uses Finset.card_image_of_injective, Sum.inr_injective

      rw [complete_bipartite_two_two_all_powers_well_covered_rightSet,
          Finset.card_image_of_injective _ Sum.inr_injective]
      simp
    
  3. The left partition class forms an independent set in K_{2,2}.

    In a complete bipartite graph, edges only run between the two parts. Any two vertices in the left partition class both have the form Sum.inl, so by definition of completeBipartiteGraph they are not adjacent.

    lines 27–33

    uses Finset.mem_coe, Finset.mem_image, Finset.mem_univ, true_and

      intro u hu v hv hne
      simp only [complete_bipartite_two_two_all_powers_well_covered_leftSet,
                 Finset.mem_coe, Finset.mem_image, Finset.mem_univ, true_and] at hu hv
      obtain ⟨a, rfl⟩ := hu
      obtain ⟨b, rfl⟩ := hv
      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
    
  4. The right partition class forms an independent set in K_{2,2}.

    Similarly, any two vertices in the right partition class both have the form Sum.inr, so they are not adjacent in K_{2,2}.

    lines 37–43

    uses Finset.mem_coe, Finset.mem_image, Finset.mem_univ, true_and

      intro u hu v hv hne
      simp only [complete_bipartite_two_two_all_powers_well_covered_rightSet,
                 Finset.mem_coe, Finset.mem_image, Finset.mem_univ, true_and] at hu hv
      obtain ⟨a, rfl⟩ := hu
      obtain ⟨b, rfl⟩ := hv
      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
    
  5. Every independent set in K_{2,2} is contained entirely in the left part or entirely in the right part.

    We check whether the independent set s contains any vertex from the left part. If it contains some Sum.inl a, it cannot contain any right vertex Sum.inr b because Sum.inl a and Sum.inr b are adjacent in K_{2,2}, which would contradict independence; thus s is a subset of the left part. If s contains no left vertex, every element of s must be a right vertex, so s is a subset of the right part.

    lines 50–68

      by_cases hleft : ∃ a : Fin 2, Sum.inl a ∈ s
      · left
        obtain ⟨a, ha⟩ := hleft
        intro x hx
        rcases x with b | b
        · simp [complete_bipartite_two_two_all_powers_well_covered_leftSet]
        · exfalso
          have hadj : complete_bipartite_two_two_all_powers_well_covered_K22.Adj
              (Sum.inl a) (Sum.inr b) := by
            simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
          have hne : (Sum.inl a : Fin 2 ⊕ Fin 2) ≠ Sum.inr b := by simp
          exact hs (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hx) hne hadj
      · right
        intro x hx
        rcases x with b | b
        · exfalso
          exact hleft ⟨b, hx⟩
        · simp [complete_bipartite_two_two_all_powers_well_covered_rightSet]
    
  6. Every maximal independent set in K_{2,2} has cardinality 2.

    Any independent set s is a subset of either the left or the right partition class. Since both partition classes are themselves independent sets, the maximality of s forces s to be equal to that entire partition class by antisymmetry of inclusion. Since each partition class has cardinality 2, |s| = 2.

    lines 75–82

    uses complete_bipartite_two_two_all_powers_well_covered_indep_subset, le_antisymm, complete_bipartite_two_two_all_powers_well_covered_leftSet_indep, complete_bipartite_two_two_all_powers_well_covered_leftSet_card, complete_bipartite_two_two_all_powers_well_covered_rightSet_indep, complete_bipartite_two_two_all_powers_well_covered_rightSet_card

      rcases complete_bipartite_two_two_all_powers_well_covered_indep_subset s hs.1 with h | h
      · have h_eq : s = complete_bipartite_two_two_all_powers_well_covered_leftSet :=
          le_antisymm h (hs.2 complete_bipartite_two_two_all_powers_well_covered_leftSet_indep h)
        rw [h_eq, complete_bipartite_two_two_all_powers_well_covered_leftSet_card]
      · have h_eq : s = complete_bipartite_two_two_all_powers_well_covered_rightSet :=
          le_antisymm h (hs.2 complete_bipartite_two_two_all_powers_well_covered_rightSet_indep h)
        rw [h_eq, complete_bipartite_two_two_all_powers_well_covered_rightSet_card]
    
  7. K_{2,2} is well-covered.

    A graph is well-covered if all its maximal independent sets have the same size. For any two maximal independent sets s and t in K_{2,2}, both have cardinality 2, hence |s| = |t|.

    lines 85–88

    uses complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card

      intro s t hs ht
      rw [complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card s hs,
          complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card t ht]
    
  8. The first power G^1 of any graph G is equal to G itself.

    Two vertices u and v are adjacent in G^1 if and only if u ≠ v and the shortest-path distance between them is at most 1. By edist_le_one_iff_adj_or_eq, distance at most 1 means u and v are adjacent or equal. With u ≠ v, this is equivalent to adjacency in G.

    lines 92–102

    uses edist_le_one_iff_adj_or_eq, Or.inl

      ext u v
      show u ≠ v ∧ G.edist u v ≤ (1 : ℕ) ↔ G.Adj u v
      norm_cast
      rw [edist_le_one_iff_adj_or_eq]
      constructor
      · rintro ⟨hne, h | rfl⟩
        · exact h
        · exact (hne rfl).elim
      · intro h
        exact ⟨h.ne, Or.inl h⟩
    
  9. The distance between any two vertices in K_{2,2} is at most 2.

    We check the four combinations for vertices u and v. If both are on the left, each is adjacent to the right vertex Sum.inr 0, so by the triangle inequality edist(u, v) ≤ 1 + 1 = 2. If one is on the left and the other on the right, they are adjacent, so the distance is 1 ≤ 2. The case with right and left is symmetric. If both are on the right, each is adjacent to the left vertex Sum.inl 0, so again edist(u, v) ≤ 1 + 1 = 2.

    lines 106–143

    uses SimpleGraph.edist_triangle, edist_eq_one_iff_adj

      rcases u with a | a <;> rcases v with b | b
      · have h1 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inl a) (Sum.inr 0) := by
          simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
        have h2 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inr 0) (Sum.inl b) := by
          simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
        have h1_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl a) (Sum.inr 0) = 1 :=
          edist_eq_one_iff_adj.mpr h1
        have h2_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr 0) (Sum.inl b) = 1 :=
          edist_eq_one_iff_adj.mpr h2
        have h_tri : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl a) (Sum.inl b) ≤
            complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl a) (Sum.inr 0) +
            complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr 0) (Sum.inl b) :=
          SimpleGraph.edist_triangle
        rw [h1_dist, h2_dist] at h_tri
        exact h_tri
      · have h : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inl a) (Sum.inr b) := by
          simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
        rw [edist_eq_one_iff_adj.mpr h]
        decide
      · have h : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inr a) (Sum.inl b) := by
          simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
        rw [edist_eq_one_iff_adj.mpr h]
        decide
      · have h1 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inr a) (Sum.inl 0) := by
          simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
        have h2 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inl 0) (Sum.inr b) := by
          simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]
        have h1_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr a) (Sum.inl 0) = 1 :=
          edist_eq_one_iff_adj.mpr h1
        have h2_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl 0) (Sum.inr b) = 1 :=
          edist_eq_one_iff_adj.mpr h2
        have h_tri : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr a) (Sum.inr b) ≤
            complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr a) (Sum.inl 0) +
            complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl 0) (Sum.inr b) :=
          SimpleGraph.edist_triangle
        rw [h1_dist, h2_dist] at h_tri
        exact h_tri
    
  10. For every d ≥ 2, the d-th power of K_{2,2} is the complete graph ⊤.

    Distinct vertices u and v are adjacent in the d-th power if their distance is at most d. Since the distance between any two vertices in K_{2,2} is at most 2 and 2 ≤ d, every pair of distinct vertices is adjacent in the d-th power, which is the definition of the complete graph ⊤.

    lines 147–152

    uses complete_bipartite_two_two_all_powers_well_covered_edist_le_two

      ext u v
      simp only [simple_graph_power, top_adj]
      refine ⟨fun h => h.1, fun h => ⟨h,
        (complete_bipartite_two_two_all_powers_well_covered_edist_le_two u v).trans ?_⟩⟩
      exact_mod_cast hd
    
  11. Any independent set in the complete graph ⊤ has cardinality at most 1.

    In the complete graph, every pair of distinct vertices is adjacent. Hence an independent set cannot contain two distinct vertices, which means its cardinality is at most 1.

    lines 156–160

    uses Finset.card_le_one_iff

      rw [Finset.card_le_one_iff]
      intro u v hu hv
      by_contra hne
      exact hs hu hv hne hne
    
  12. In any graph, every singleton vertex set is an independent set.

    A singleton set cannot contain two distinct vertices, so the independence condition holds vacuously.

    lines 164–168

    uses False.elim

      intro a ha b hb hab
      simp only [Set.mem_singleton_iff] at ha hb
      rw [ha, hb] at hab
      exact False.elim (hab rfl)
    
  13. The complete graph ⊤ on any nonempty finite vertex type is well-covered.

    Every maximal independent set u has cardinality at most 1 by top_indep_card_le_one. If u were empty, then any singleton {x} (which exists because the vertex type is nonempty) would be an independent set strictly containing u, contradicting the maximality of u. Hence u is nonempty, giving |u| ≥ 1, so |u| = 1. Since every maximal independent set has cardinality 1, any two have the same size.

    lines 172–191

    uses complete_bipartite_two_two_all_powers_well_covered_top_indep_card_le_one, Finset.not_nonempty_iff_eq_empty, Finset.coe_singleton, complete_bipartite_two_two_all_powers_well_covered_singleton_is_indep, Finset.empty_subset, Finset.mem_singleton_self, Finset.notMem_empty, le_antisymm

      intro s t hs ht
      have h_card (u : Finset V)
          (hu : Maximal (fun (x : Finset V) => (⊤ : SimpleGraph V).IsIndepSet (x : Set V)) u) :
          u.card = 1 := by
        have hle := complete_bipartite_two_two_all_powers_well_covered_top_indep_card_le_one u hu.1
        have hne : u.Nonempty := by
          by_contra he
          rw [Finset.not_nonempty_iff_eq_empty] at he
          subst he
          obtain ⟨x⟩ := ‹Nonempty V›
          have hsing : (⊤ : SimpleGraph V).IsIndepSet (({x} : Finset V) : Set V) := by
            simp only [Finset.coe_singleton]
            exact complete_bipartite_two_two_all_powers_well_covered_singleton_is_indep ⊤ x
          have hle_empty : (∅ : Finset V) ≤ {x} := Finset.empty_subset _
          have hmax := hu.2 hsing hle_empty
          have : x ∈ (∅ : Finset V) := hmax (Finset.mem_singleton_self x)
          exact Finset.notMem_empty x this
        exact le_antisymm hle (Finset.card_pos.mpr hne)
      rw [h_card s hs, h_card t ht]
    
  14. For d = 1, the power graph K_{2,2}^1 is well-covered.

    From 1 ≤ d, we split into cases d = 1 and 2 ≤ d. When d = 1, the power graph K_{2,2}^1 equals K_{2,2}, which was already proved to be well-covered.

    lines 195–198

    uses complete_bipartite_two_two_all_powers_well_covered_power_one_eq_self, complete_bipartite_two_two_all_powers_well_covered_K22_well_covered

      intro d hd
      obtain rfl | hd2 : d = 1 ∨ 2 ≤ d := by omega
      · rw [complete_bipartite_two_two_all_powers_well_covered_power_one_eq_self]
        exact complete_bipartite_two_two_all_powers_well_covered_K22_well_covered
  15. For d ≥ 2, the power graph K_{2,2}^d is well-covered.

    When 2 ≤ d, the d-th power graph of K_{2,2} equals the complete graph ⊤ on Fin 2 ⊕ Fin 2. Since this vertex type is finite and nonempty, ⊤ is well-covered.

    lines 199–201

    uses complete_bipartite_two_two_all_powers_well_covered_power_ge_two_eq_top, complete_bipartite_two_two_all_powers_well_covered_well_covered_top

      · change simple_graph_is_well_covered (simple_graph_power complete_bipartite_two_two_all_powers_well_covered_K22 d)
        rw [complete_bipartite_two_two_all_powers_well_covered_power_ge_two_eq_top _ hd2]
        exact complete_bipartite_two_two_all_powers_well_covered_well_covered_top
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the domain set.
Sum.inl_injective
The canonical injection Sum.inl into a sum type is injective.
Sum.inr_injective
The canonical injection Sum.inr into a sum type is injective.
Finset.mem_coe
An element belongs to a finset coerced to a set if and only if it belongs to the finset.
Finset.mem_image
An element belongs to the image of a finset under f if and only if it is the image of some element in the finset.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
true_and
A conjunction True ∧ p is logically equivalent to p.
complete_bipartite_two_two_all_powers_well_covered_indep_subset
Every independent set in K_{2,2} is a subset of either the left or the right partition class.
le_antisymm
In a partial order, if a ≤ b and b ≤ a then a = b.
complete_bipartite_two_two_all_powers_well_covered_leftSet_indep
The left partition class of K_{2,2} is an independent set.
complete_bipartite_two_two_all_powers_well_covered_leftSet_card
The left partition class of K_{2,2} has cardinality 2.
complete_bipartite_two_two_all_powers_well_covered_rightSet_indep
The right partition class of K_{2,2} is an independent set.
complete_bipartite_two_two_all_powers_well_covered_rightSet_card
The right partition class of K_{2,2} has cardinality 2.
complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card
Every maximal independent set in K_{2,2} has cardinality 2.
edist_le_one_iff_adj_or_eq
The distance between two vertices in a graph is at most 1 if and only if they are adjacent or equal.
Or.inl
From a proposition a, infer the disjunction a ∨ b.
edist_eq_one_iff_adj
The distance between two vertices in a graph is 1 if and only if they are adjacent.
SimpleGraph.edist_triangle
The shortest-path distance in a graph satisfies the triangle inequality.
complete_bipartite_two_two_all_powers_well_covered_edist_le_two
The shortest-path distance between any two vertices in K_{2,2} is at most 2.
Finset.card_le_one_iff
A finite set has cardinality at most 1 if and only if every pair of elements in it are equal.
False.elim
From False, any proposition follows (principle of explosion).
complete_bipartite_two_two_all_powers_well_covered_top_indep_card_le_one
Any independent set in the complete graph ⊤ has cardinality at most 1.
Finset.not_nonempty_iff_eq_empty
A finite set is not nonempty if and only if it is the empty set.
Finset.coe_singleton
The coercion of a singleton finset {a} to a set is the singleton set {a}.
complete_bipartite_two_two_all_powers_well_covered_singleton_is_indep
In any graph, every singleton set of vertices is an independent set.
Finset.empty_subset
The empty set is a subset of every finite set.
Finset.mem_singleton_self
Every element belongs to its own singleton set.
Finset.notMem_empty
The empty set has no members.
complete_bipartite_two_two_all_powers_well_covered_power_one_eq_self
The 1st power of any graph G is equal to G itself.
complete_bipartite_two_two_all_powers_well_covered_K22_well_covered
The complete bipartite graph K_{2,2} is well-covered.
complete_bipartite_two_two_all_powers_well_covered_power_ge_two_eq_top
For any integer d ≥ 2, the d-th power of K_{2,2} is the complete graph ⊤.
complete_bipartite_two_two_all_powers_well_covered_well_covered_top
The complete graph ⊤ on any nonempty finite vertex type 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

open SimpleGraphprivate def complete_bipartite_two_two_all_powers_well_covered_K22 :=  completeBipartiteGraph (Fin 2) (Fin 2)private def complete_bipartite_two_two_all_powers_well_covered_leftSet :    Finset (Fin 2 ⊕ Fin 2) := Finset.univ.image Sum.inlprivate def complete_bipartite_two_two_all_powers_well_covered_rightSet :    Finset (Fin 2 ⊕ Fin 2) := Finset.univ.image Sum.inrprivate lemma complete_bipartite_two_two_all_powers_well_covered_leftSet_card :    complete_bipartite_two_two_all_powers_well_covered_leftSet.card = 2 := by  rw [complete_bipartite_two_two_all_powers_well_covered_leftSet,      Finset.card_image_of_injective _ Sum.inl_injective]  simpprivate lemma complete_bipartite_two_two_all_powers_well_covered_rightSet_card :    complete_bipartite_two_two_all_powers_well_covered_rightSet.card = 2 := by  rw [complete_bipartite_two_two_all_powers_well_covered_rightSet,      Finset.card_image_of_injective _ Sum.inr_injective]  simpprivate lemma complete_bipartite_two_two_all_powers_well_covered_leftSet_indep :    complete_bipartite_two_two_all_powers_well_covered_K22.IsIndepSet      (complete_bipartite_two_two_all_powers_well_covered_leftSet : Set (Fin 2 ⊕ Fin 2)) := by  intro u hu v hv hne  simp only [complete_bipartite_two_two_all_powers_well_covered_leftSet,             Finset.mem_coe, Finset.mem_image, Finset.mem_univ, true_and] at hu hv  obtain ⟨a, rfl⟩ := hu  obtain ⟨b, rfl⟩ := hv  simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]private lemma complete_bipartite_two_two_all_powers_well_covered_rightSet_indep :    complete_bipartite_two_two_all_powers_well_covered_K22.IsIndepSet      (complete_bipartite_two_two_all_powers_well_covered_rightSet : Set (Fin 2 ⊕ Fin 2)) := by  intro u hu v hv hne  simp only [complete_bipartite_two_two_all_powers_well_covered_rightSet,             Finset.mem_coe, Finset.mem_image, Finset.mem_univ, true_and] at hu hv  obtain ⟨a, rfl⟩ := hu  obtain ⟨b, rfl⟩ := hv  simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]private lemma complete_bipartite_two_two_all_powers_well_covered_indep_subset    (s : Finset (Fin 2 ⊕ Fin 2))    (hs : complete_bipartite_two_two_all_powers_well_covered_K22.IsIndepSet      (s : Set (Fin 2 ⊕ Fin 2))) :    s ⊆ complete_bipartite_two_two_all_powers_well_covered_leftSet ∨    s ⊆ complete_bipartite_two_two_all_powers_well_covered_rightSet := by  by_cases hleft : ∃ a : Fin 2, Sum.inl a ∈ s  · left    obtain ⟨a, ha⟩ := hleft    intro x hx    rcases x with b | b    · simp [complete_bipartite_two_two_all_powers_well_covered_leftSet]    · exfalso      have hadj : complete_bipartite_two_two_all_powers_well_covered_K22.Adj          (Sum.inl a) (Sum.inr b) := by        simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]      have hne : (Sum.inl a : Fin 2 ⊕ Fin 2) ≠ Sum.inr b := by simp      exact hs (Finset.mem_coe.mpr ha) (Finset.mem_coe.mpr hx) hne hadj  · right    intro x hx    rcases x with b | b    · exfalso      exact hleft ⟨b, hx⟩    · simp [complete_bipartite_two_two_all_powers_well_covered_rightSet]private lemma complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card    (s : Finset (Fin 2 ⊕ Fin 2))    (hs : Maximal (fun (u : Finset (Fin 2 ⊕ Fin 2)) =>      complete_bipartite_two_two_all_powers_well_covered_K22.IsIndepSet        (u : Set (Fin 2 ⊕ Fin 2))) s) :    s.card = 2 := by  rcases complete_bipartite_two_two_all_powers_well_covered_indep_subset s hs.1 with h | h  · have h_eq : s = complete_bipartite_two_two_all_powers_well_covered_leftSet :=      le_antisymm h (hs.2 complete_bipartite_two_two_all_powers_well_covered_leftSet_indep h)    rw [h_eq, complete_bipartite_two_two_all_powers_well_covered_leftSet_card]  · have h_eq : s = complete_bipartite_two_two_all_powers_well_covered_rightSet :=      le_antisymm h (hs.2 complete_bipartite_two_two_all_powers_well_covered_rightSet_indep h)    rw [h_eq, complete_bipartite_two_two_all_powers_well_covered_rightSet_card]private lemma complete_bipartite_two_two_all_powers_well_covered_K22_well_covered :    simple_graph_is_well_covered complete_bipartite_two_two_all_powers_well_covered_K22 := by  intro s t hs ht  rw [complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card s hs,      complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_card t ht]private lemma complete_bipartite_two_two_all_powers_well_covered_power_one_eq_self    {V : Type*} (G : SimpleGraph V) :    simple_graph_power G 1 = G := by  ext u v  show u ≠ v ∧ G.edist u v ≤ (1 : ℕ) ↔ G.Adj u v  norm_cast  rw [edist_le_one_iff_adj_or_eq]  constructor  · rintro ⟨hne, h | rfl⟩    · exact h    · exact (hne rfl).elim  · intro h    exact ⟨h.ne, Or.inl h⟩private lemma complete_bipartite_two_two_all_powers_well_covered_edist_le_two    (u v : Fin 2 ⊕ Fin 2) :    complete_bipartite_two_two_all_powers_well_covered_K22.edist u v ≤ 2 := by  rcases u with a | a <;> rcases v with b | b  · have h1 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inl a) (Sum.inr 0) := by      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]    have h2 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inr 0) (Sum.inl b) := by      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]    have h1_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl a) (Sum.inr 0) = 1 :=      edist_eq_one_iff_adj.mpr h1    have h2_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr 0) (Sum.inl b) = 1 :=      edist_eq_one_iff_adj.mpr h2    have h_tri : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl a) (Sum.inl b) ≤        complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl a) (Sum.inr 0) +        complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr 0) (Sum.inl b) :=      SimpleGraph.edist_triangle    rw [h1_dist, h2_dist] at h_tri    exact h_tri  · have h : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inl a) (Sum.inr b) := by      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]    rw [edist_eq_one_iff_adj.mpr h]    decide  · have h : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inr a) (Sum.inl b) := by      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]    rw [edist_eq_one_iff_adj.mpr h]    decide  · have h1 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inr a) (Sum.inl 0) := by      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]    have h2 : complete_bipartite_two_two_all_powers_well_covered_K22.Adj (Sum.inl 0) (Sum.inr b) := by      simp [complete_bipartite_two_two_all_powers_well_covered_K22, completeBipartiteGraph]    have h1_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr a) (Sum.inl 0) = 1 :=      edist_eq_one_iff_adj.mpr h1    have h2_dist : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl 0) (Sum.inr b) = 1 :=      edist_eq_one_iff_adj.mpr h2    have h_tri : complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr a) (Sum.inr b) ≤        complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inr a) (Sum.inl 0) +        complete_bipartite_two_two_all_powers_well_covered_K22.edist (Sum.inl 0) (Sum.inr b) :=      SimpleGraph.edist_triangle    rw [h1_dist, h2_dist] at h_tri    exact h_triprivate lemma complete_bipartite_two_two_all_powers_well_covered_power_ge_two_eq_top    (d : ℕ) (hd : 2 ≤ d) :    simple_graph_power complete_bipartite_two_two_all_powers_well_covered_K22 d = ⊤ := by  ext u v  simp only [simple_graph_power, top_adj]  refine ⟨fun h => h.1, fun h => ⟨h,    (complete_bipartite_two_two_all_powers_well_covered_edist_le_two u v).trans ?_⟩⟩  exact_mod_cast hdprivate lemma complete_bipartite_two_two_all_powers_well_covered_top_indep_card_le_one    {V : Type*} (s : Finset V)    (hs : (⊤ : SimpleGraph V).IsIndepSet (s : Set V)) : s.card ≤ 1 := by  rw [Finset.card_le_one_iff]  intro u v hu hv  by_contra hne  exact hs hu hv hne hneprivate lemma complete_bipartite_two_two_all_powers_well_covered_singleton_is_indep    {V : Type*} (G : SimpleGraph V) (v : V) :    G.IsIndepSet ({v} : Set V) := by  intro a ha b hb hab  simp only [Set.mem_singleton_iff] at ha hb  rw [ha, hb] at hab  exact False.elim (hab rfl)private lemma complete_bipartite_two_two_all_powers_well_covered_well_covered_top    {V : Type*} [Fintype V] [Nonempty V] :    simple_graph_is_well_covered (⊤ : SimpleGraph V) := by  intro s t hs ht  have h_card (u : Finset V)      (hu : Maximal (fun (x : Finset V) => (⊤ : SimpleGraph V).IsIndepSet (x : Set V)) u) :      u.card = 1 := by    have hle := complete_bipartite_two_two_all_powers_well_covered_top_indep_card_le_one u hu.1    have hne : u.Nonempty := by      by_contra he      rw [Finset.not_nonempty_iff_eq_empty] at he      subst he      obtain ⟨x⟩ := ‹Nonempty V›      have hsing : (⊤ : SimpleGraph V).IsIndepSet (({x} : Finset V) : Set V) := by        simp only [Finset.coe_singleton]        exact complete_bipartite_two_two_all_powers_well_covered_singleton_is_indep ⊤ x      have hle_empty : (∅ : Finset V) ≤ {x} := Finset.empty_subset _      have hmax := hu.2 hsing hle_empty      have : x ∈ (∅ : Finset V) := hmax (Finset.mem_singleton_self x)      exact Finset.notMem_empty x this    exact le_antisymm hle (Finset.card_pos.mpr hne)  rw [h_card s hs, h_card t ht]/-- Every power of the complete bipartite graph K_{2,2} is well-covered. -/theorem complete_bipartite_two_two_all_powers_well_covered :    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (completeBipartiteGraph (Fin 2) (Fin 2)) d) := by  intro d hd  obtain rfl | hd2 : d = 1 ∨ 2 ≤ d := by omega  · rw [complete_bipartite_two_two_all_powers_well_covered_power_one_eq_self]    exact complete_bipartite_two_two_all_powers_well_covered_K22_well_covered  · change simple_graph_is_well_covered (simple_graph_power complete_bipartite_two_two_all_powers_well_covered_K22 d)    rw [complete_bipartite_two_two_all_powers_well_covered_power_ge_two_eq_top _ hd2]    exact complete_bipartite_two_two_all_powers_well_covered_well_covered_top
See it in the graphDiscuss this resultChallenge it