complete_bipartite_two_two_all_powers_well_covered
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.
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.
uses
Finset.card_image_of_injective,Sum.inl_injectiverw [complete_bipartite_two_two_all_powers_well_covered_leftSet, Finset.card_image_of_injective _ Sum.inl_injective] simp
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.
uses
Finset.card_image_of_injective,Sum.inr_injectiverw [complete_bipartite_two_two_all_powers_well_covered_rightSet, Finset.card_image_of_injective _ Sum.inr_injective] simp
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.
uses
Finset.mem_coe,Finset.mem_image,Finset.mem_univ,true_andintro 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]
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}.
uses
Finset.mem_coe,Finset.mem_image,Finset.mem_univ,true_andintro 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]
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.
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]
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.
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_cardrcases 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]
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|.
uses
complete_bipartite_two_two_all_powers_well_covered_K22_maximal_indep_cardintro 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]
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.
uses
edist_le_one_iff_adj_or_eq,Or.inlext 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⟩
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.
uses
SimpleGraph.edist_triangle,edist_eq_one_iff_adjrcases 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
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 ⊤.
uses
complete_bipartite_two_two_all_powers_well_covered_edist_le_twoext 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
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.
uses
Finset.card_le_one_iffrw [Finset.card_le_one_iff] intro u v hu hv by_contra hne exact hs hu hv hne hne
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.
uses
False.elimintro a ha b hb hab simp only [Set.mem_singleton_iff] at ha hb rw [ha, hb] at hab exact False.elim (hab rfl)
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.
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_antisymmintro 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]
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.
uses
complete_bipartite_two_two_all_powers_well_covered_power_one_eq_self,complete_bipartite_two_two_all_powers_well_covered_K22_well_coveredintro 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
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.
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.
- The vertices of K_{2,2} are formalized as the sum type `Fin 2 ⊕ Fin 2`, with the two bipartition classes given by the canonical inclusions `Sum.inl` and `Sum.inr`.
- In Step 14, the case split d = 1 ∨ 2 ≤ d from the hypothesis 1 ≤ d is handled automatically by the linear integer arithmetic tactic `omega`.
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.
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