not_planar_all_powers_well_covered_characterization
It is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is either a complete graph of order at most 4 or a clique blow-up of the 5-cycle C_5.
Statement
theorem not_planar_all_powers_well_covered_characterization : ¬ (∀ {V : Type} [Fintype V] (G : SimpleGraph V), G.Connected → simple_graph_is_planar G → 2 ≤ Fintype.card V → (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) → (∃ k : ℕ, k ≤ 4 ∧ Nonempty (G ≃g (⊤ : SimpleGraph (Fin k)))) ∨ (∃ a : Fin 5 → ℕ, (∀ i, 0 < a i) ∧ Nonempty (simple_graph_clique_blowup (SimpleGraph.cycleGraph 5) a ≃g G)))
- Formalizes
- arXiv:2610.09300 after Theorem 1.4 -- On graphs whose powers are well-covered
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- simple_graph_is_planarA simple graph G is planar by Wagner's criterion if neither the complete graph on 5 vertices nor the complete bipartite graph K_{3,3} is a…
- 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…
- simple_graph_clique_blowupThe clique blow-up H = G[K_{a_1}, …, K_{a_n}]: each vertex v_i of G is replaced by a clique Q_i on a_i vertices, and distinct vertices x ∈…
- forall_power_well_covered_of_well_covered_diam_le_twoLet G be a finite connected well-covered graph of diameter at most 2. Then G^d is well-covered for every d ≥ 1.
- simple_graph_is_minorA graph H is a minor of a graph G if there exists a family of pairwise disjoint, non-empty, connected subsets B_u of V(G) indexed by u in…
- g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Read back from the Lean
The theorem asserts the negation of the following claim:
For every finite type V and every simple graph G on V, if:
1. G is connected,
2. G is planar (defined here as having neither $K_5$ nor $K_{3,3}$ as a graph minor),
3. V has at least 2 elements (2 ≤ Fintype.card V), and
4. for every natural number $d \ge 1$, the $d$-th power of $G$ is well-covered (every maximal independent set in the $d$-th power of $G$ has the same cardinality),
then at least one of the following two alternatives holds:
- There exists $k \le 4$ such that $G$ is isomorphic to the complete graph on $k$ vertices ($K_k$), or
- There exists a function $a : \text{Fin } 5 \to \mathbb{N}$ with $a(i) > 0$ for all $i \in \text{Fin } 5$ such that $G$ is isomorphic to the clique blowup of the 5-cycle ($C_5$) with clique sizes given by $a$.
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
The proposed characterization asserts that every finite connected planar graph with at least two vertices whose powers are all well-covered must be a complete graph of order at most 4 or a clique blow-up of C_5. This theorem refutes that characterization by demonstrating that the 4-cycle C_4 is a counterexample. C_4 is connected, planar, and well-covered with diameter 2, which ensures that all of its graph powers are well-covered; however, C_4 is neither complete (having non-adjacent vertices) nor a blow-up of C_5 (which requires at least 5 vertices).
A graph cannot contain a minor with strictly more vertices than itself.
Assume for contradiction that H is a minor of G with |V(G)| < |V(H)|. By definition of a graph minor, there exists a family of pairwise disjoint, non-empty connected branch sets B(u) ⊆ V(G) for each vertex u of H. Choosing an element f(u) ∈ B(u) for each u defines a function f : V(H) → V(G), which is injective because the branch sets are disjoint. The existence of an injection implies |V(H)| ≤ |V(G)|, contradicting |V(G)| < |V(H)|.
uses
Set.disjoint_iff.mp,not_lt_of_ge,Fintype.card_le_of_injectiveclassical intro ⟨B, hconn, hdisj, _⟩ have hnonempty : ∀ u, ∃ x, x ∈ B u := fun u => (hconn u).nonempty.elim (fun ⟨x, hx⟩ => ⟨x, hx⟩) choose f hf using hnonempty have hinj : Function.Injective f := by intro u v huv by_contra hne have hd := hdisj u v hne exact Set.disjoint_iff.mp hd ⟨hf u, huv ▸ hf v⟩ exact absurd h (not_lt_of_ge (Fintype.card_le_of_injective f hinj))
Every graph with at most 4 vertices is planar.
Planarity is defined by the absence of K_5 and K_{3,3} minors. Since the host graph has at most 4 vertices, while K_5 has 5 vertices and K_{3,3} has 6 vertices, linear arithmetic confirms that the host has strictly fewer vertices than either test graph. Applying the minor-cardinality lemma excludes both minors, establishing planarity.
uses
not_planar_all_powers_well_covered_characterization_not_minor_of_card_ltunfold simple_graph_is_planar refine ⟨not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt _ _ ?_, not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt _ _ ?_⟩ · simp; omega · simp; omega
Any two vertices in the 4-cycle C_4 are equal, adjacent, or share a common neighbor. automation
The property holds for all pairs of vertices in Fin 4 by exhaustive computation (`decide`).
decideThe extended distance between any two vertices in C_4 is at most 2.
We case-split on the preceding trichotomy: if u = v, the distance is 0; if u is adjacent to v, the 1-edge walk gives distance at most 1; if they share a common neighbor w, the 2-edge walk through w gives distance at most 2.
uses
not_planar_all_powers_well_covered_characterization_c4_dist_le_two_aux,SimpleGraph.edist_selfrcases not_planar_all_powers_well_covered_characterization_c4_dist_le_two_aux u v with rfl | h | ⟨w, h1, h2⟩ · rw [SimpleGraph.edist_self]; norm_num · exact (SimpleGraph.Walk.cons h SimpleGraph.Walk.nil).edist_le.trans (by simp) · exact (SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2 SimpleGraph.Walk.nil)).edist_le.trans (by simp)
The diameter of C_4 is at most 2.
Since the extended distance between any pair of vertices is at most 2, the extended diameter ediam(C_4) is at most 2. Converting from extended natural numbers to ℕ gives diam(C_4) ≤ 2.
uses
SimpleGraph.ediam_le_iff,not_planar_all_powers_well_covered_characterization_c4_edist_le_two,ENat.toNat_le_of_le_natCasthave hediam : (SimpleGraph.cycleGraph 4).ediam ≤ 2 := by rw [SimpleGraph.ediam_le_iff] exact not_planar_all_powers_well_covered_characterization_c4_edist_le_two rw [SimpleGraph.diam] exact ENat.toNat_le_of_le_natCast hediam
Every independent set in C_4 contains at most 2 vertices. automation
Verified by exhaustive search over all subsets of Fin 4 using `decide`.
revert s hs decideAny independent set in C_4 with fewer than 2 vertices can be extended by adding another vertex. automation
Verified by exhaustive search over all subsets of Fin 4 with cardinality strictly less than 2 using `decide`.
revert s hs hcard decideEvery maximal independent set in C_4 has cardinality exactly 2.
Let s be a maximal independent set. We have |s| ≤ 2 by the upper bound. If |s| < 2, the extension lemma provides a vertex v ∉ s such that s ∪ {v} is independent. By maximality of s, s ∪ {v} ⊆ s, which implies v ∈ s, a contradiction. Thus |s| = 2.
uses
not_planar_all_powers_well_covered_characterization_c4_indep_card_le_two,not_planar_all_powers_well_covered_characterization_c4_indep_extend,Finset.subset_insert,Finset.mem_insert_selfhave hle : s.card ≤ 2 := not_planar_all_powers_well_covered_characterization_c4_indep_card_le_two s hs.1 have hge : 2 ≤ s.card := by by_contra! hlt obtain ⟨v, hv_notin, hv_indep⟩ := not_planar_all_powers_well_covered_characterization_c4_indep_extend s hs.1 hlt have hsub : s ≤ insert v s := Finset.subset_insert v s have heq : insert v s ≤ s := hs.2 hv_indep hsub exact hv_notin (heq (Finset.mem_insert_self v s)) omega
The 4-cycle C_4 is well-covered.
A graph is well-covered if all maximal independent sets have the same size. Since every maximal independent set in C_4 has size 2, any two maximal independent sets s and t have |s| = 2 = |t|.
uses
not_planar_all_powers_well_covered_characterization_c4_maximal_cardintro s t hs ht rw [not_planar_all_powers_well_covered_characterization_c4_maximal_card s hs, not_planar_all_powers_well_covered_characterization_c4_maximal_card t ht]
Every power C_4^d of C_4 (for d ≥ 1) is well-covered.
The graph C_4 is connected, has diameter at most 2, and is well-covered. Applying the knowledge base theorem forall_power_well_covered_of_well_covered_diam_le_two directly implies that all its graph powers are well-covered.
uses
SimpleGraph.cycleGraph_connected,forall_power_well_covered_of_well_covered_diam_le_two,not_planar_all_powers_well_covered_characterization_c4_diam_le_two,not_planar_all_powers_well_covered_characterization_c4_is_well_coveredhave hconn : (SimpleGraph.cycleGraph 4).Connected := @SimpleGraph.cycleGraph_connected 3 exact forall_power_well_covered_of_well_covered_diam_le_two (SimpleGraph.cycleGraph 4) hconn not_planar_all_powers_well_covered_characterization_c4_diam_le_two not_planar_all_powers_well_covered_characterization_c4_is_well_covered
The 4-cycle C_4 is not isomorphic to any complete graph of order at most 4.
Suppose e is an isomorphism from C_4 to K_k with k ≤ 4. Comparing vertex counts gives k = 4. In K_4, the vertices e(0) and e(2) are adjacent because e is injective and 0 ≠ 2. Transporting this adjacency back across e implies that 0 and 2 are adjacent in C_4, which is false by direct computation (`decide`).
uses
Fintype.card_congr,Fintype.card_fin,SimpleGraph.top_adjintro ⟨k, hk, ⟨e⟩⟩ have hcard : Fintype.card (Fin 4) = Fintype.card (Fin k) := Fintype.card_congr e.toEquiv simp only [Fintype.card_fin] at hcard subst hcard have hadj : (⊤ : SimpleGraph (Fin 4)).Adj (e 0) (e 2) := by rw [SimpleGraph.top_adj] intro h have : (0 : Fin 4) = 2 := e.injective h revert this; decide have h_c4 : (SimpleGraph.cycleGraph 4).Adj 0 2 := e.map_adj_iff.mp hadj revert h_c4 decide
The 4-cycle C_4 is not isomorphic to any clique blow-up of C_5 with positive weights.
In a clique blow-up of C_5 with weights a_i ≥ 1, the total number of vertices is ∑_{i=0}^4 a_i ≥ 5 * 1 = 5. An isomorphism to C_4 would require this sum to equal |V(C_4)| = 4, which contradicts 5 ≤ 4.
uses
Fintype.card_congr,Fintype.card_sigma,Fintype.card_fin,Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,nsmul_eq_mul,mul_oneintro ⟨a, ha, ⟨e⟩⟩ have hcard : Fintype.card (Σ i : Fin 5, Fin (a i)) = Fintype.card (Fin 4) := Fintype.card_congr e.toEquiv rw [Fintype.card_sigma] at hcard simp only [Fintype.card_fin] at hcard have hsum : 5 ≤ ∑ i : Fin 5, a i := by have : ∑ i : Fin 5, (1 : ℕ) ≤ ∑ i : Fin 5, a i := Finset.sum_le_sum (fun i _ => ha i) simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] at this exact this omega
The characterization fails: not every connected planar graph with all powers well-covered is a complete graph of order at most 4 or a clique blow-up of C_5.
Assuming the universal characterization, we apply it to G = C_4. C_4 is connected, planar (having 4 vertices), has at least 2 vertices, and all its powers are well-covered. The characterization would require C_4 to be isomorphic to K_k for some k ≤ 4 or to be a clique blow-up of C_5. Both cases are refuted by the preceding non-isomorphism lemmas, yielding a contradiction.
uses
SimpleGraph.cycleGraph_connected,not_planar_all_powers_well_covered_characterization_planar_of_card_le_four,not_planar_all_powers_well_covered_characterization_c4_all_powers_well_covered,not_planar_all_powers_well_covered_characterization_not_iso_top_c4,not_planar_all_powers_well_covered_characterization_not_iso_blowup_c4intro h have hconn : (SimpleGraph.cycleGraph 4).Connected := @SimpleGraph.cycleGraph_connected 3 have hplanar : simple_graph_is_planar (SimpleGraph.cycleGraph 4) := not_planar_all_powers_well_covered_characterization_planar_of_card_le_four _ (by decide) have hcard : 2 ≤ Fintype.card (Fin 4) := by decide have hwc := not_planar_all_powers_well_covered_characterization_c4_all_powers_well_covered rcases h (SimpleGraph.cycleGraph 4) hconn hplanar hcard hwc with h1 | h2 · exact not_planar_all_powers_well_covered_characterization_not_iso_top_c4 h1 · exact not_planar_all_powers_well_covered_characterization_not_iso_blowup_c4 h2
Set.disjoint_iff.mp- Two sets are disjoint if and only if their intersection is empty (contained in the empty set).
not_lt_of_ge- If a ≤ b, then b is not strictly less than a.
Fintype.card_le_of_injective- An injective function between finite types implies the domain's cardinality is at most the codomain's cardinality.
not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt- A finite graph G cannot have H as a minor if G has strictly fewer vertices than H.
not_planar_all_powers_well_covered_characterization_c4_dist_le_two_aux- Any two vertices in the 4-cycle C_4 are equal, adjacent, or share a common neighbor.
SimpleGraph.edist_self- The extended distance from a vertex to itself is 0.
SimpleGraph.ediam_le_iff- The extended diameter of a graph is at most k if and only if the extended distance between every pair of vertices is at most k.
not_planar_all_powers_well_covered_characterization_c4_edist_le_two- The extended distance between any two vertices in C_4 is at most 2.
ENat.toNat_le_of_le_natCast- If an extended natural number m is at most n (embedded in ENat), then its conversion to ℕ is at most n.
not_planar_all_powers_well_covered_characterization_c4_indep_card_le_two- Every independent set in C_4 has at most 2 vertices.
not_planar_all_powers_well_covered_characterization_c4_indep_extend- Any independent set in C_4 with fewer than 2 vertices can be extended by adding another vertex.
Finset.subset_insert- A finite set is a subset of the set obtained by inserting an element into it.
Finset.mem_insert_self- An element inserted into a finite set is a member of the resulting set.
not_planar_all_powers_well_covered_characterization_c4_maximal_card- Every maximal independent set in C_4 has cardinality exactly 2.
SimpleGraph.cycleGraph_connected- The cycle graph on n + 1 vertices is connected.
forall_power_well_covered_of_well_covered_diam_le_two- A connected well-covered graph of diameter at most 2 has all of its powers G^d (d ≥ 1) well-covered.
not_planar_all_powers_well_covered_characterization_c4_diam_le_two- The diameter of C_4 is at most 2.
not_planar_all_powers_well_covered_characterization_c4_is_well_covered- The cycle graph C_4 is well-covered.
Fintype.card_congr- A bijection between two finite types implies their cardinalities are equal.
Fintype.card_fin- The cardinality of Fin n is n.
SimpleGraph.top_adj- Two vertices in the complete graph ⊤ are adjacent if and only if they are distinct.
Fintype.card_sigma- The cardinality of a dependent sum (sigma type) of finite types is the sum of the cardinalities of the fibers.
Finset.sum_le_sum- If f i ≤ g i for all i in a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.sum_const- The sum of a constant value b over a finite set s is equal to |s| • b.
Finset.card_univ- The cardinality of the universal finset on a finite type α equals the cardinality of α.
nsmul_eq_mul- Scalar multiplication by a natural number n • a is equal to the product n * a.
mul_one- Multiplying any element by 1 on the right leaves it unchanged.
not_planar_all_powers_well_covered_characterization_planar_of_card_le_four- Any finite graph with at most 4 vertices is planar.
not_planar_all_powers_well_covered_characterization_c4_all_powers_well_covered- All powers C_4^d (d ≥ 1) of the 4-cycle are well-covered.
not_planar_all_powers_well_covered_characterization_not_iso_top_c4- The 4-cycle C_4 is not isomorphic to any complete graph of order at most 4.
not_planar_all_powers_well_covered_characterization_not_iso_blowup_c4- The 4-cycle C_4 is not isomorphic to any clique blow-up of C_5 with strictly positive vertex weights.
- The docstring at line 108 mentions C_7 as a counterexample, but the formal proof actually constructs the counterexample using the 4-cycle C_4.
- Finite properties of C_4 (the distance trichotomy, bounds on independent set sizes, and non-isomorphism to K_4) are verified by Lean's kernel computation using `decide`.
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.
lemma not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt {U V : Type*} [Fintype U] [Fintype V] (H : SimpleGraph U) (G : SimpleGraph V) (h : Fintype.card V < Fintype.card U) : ¬ simple_graph_is_minor H G := by classical intro ⟨B, hconn, hdisj, _⟩ have hnonempty : ∀ u, ∃ x, x ∈ B u := fun u => (hconn u).nonempty.elim (fun ⟨x, hx⟩ => ⟨x, hx⟩) choose f hf using hnonempty have hinj : Function.Injective f := by intro u v huv by_contra hne have hd := hdisj u v hne exact Set.disjoint_iff.mp hd ⟨hf u, huv ▸ hf v⟩ exact absurd h (not_lt_of_ge (Fintype.card_le_of_injective f hinj))lemma not_planar_all_powers_well_covered_characterization_planar_of_card_le_four {V : Type*} [Fintype V] (G : SimpleGraph V) (h : Fintype.card V ≤ 4) : simple_graph_is_planar G := by unfold simple_graph_is_planar refine ⟨not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt _ _ ?_, not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt _ _ ?_⟩ · simp; omega · simp; omegatheorem not_planar_all_powers_well_covered_characterization_c4_dist_le_two_aux : ∀ u v : Fin 4, u = v ∨ (SimpleGraph.cycleGraph 4).Adj u v ∨ ∃ w : Fin 4, (SimpleGraph.cycleGraph 4).Adj u w ∧ (SimpleGraph.cycleGraph 4).Adj w v := by decidetheorem not_planar_all_powers_well_covered_characterization_c4_edist_le_two (u v : Fin 4) : (SimpleGraph.cycleGraph 4).edist u v ≤ 2 := by rcases not_planar_all_powers_well_covered_characterization_c4_dist_le_two_aux u v with rfl | h | ⟨w, h1, h2⟩ · rw [SimpleGraph.edist_self]; norm_num · exact (SimpleGraph.Walk.cons h SimpleGraph.Walk.nil).edist_le.trans (by simp) · exact (SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2 SimpleGraph.Walk.nil)).edist_le.trans (by simp)theorem not_planar_all_powers_well_covered_characterization_c4_diam_le_two : (SimpleGraph.cycleGraph 4).diam ≤ 2 := by have hediam : (SimpleGraph.cycleGraph 4).ediam ≤ 2 := by rw [SimpleGraph.ediam_le_iff] exact not_planar_all_powers_well_covered_characterization_c4_edist_le_two rw [SimpleGraph.diam] exact ENat.toNat_le_of_le_natCast hediamtheorem not_planar_all_powers_well_covered_characterization_c4_indep_card_le_two (s : Finset (Fin 4)) (hs : (SimpleGraph.cycleGraph 4).IsIndepSet (s : Set (Fin 4))) : s.card ≤ 2 := by revert s hs decidetheorem not_planar_all_powers_well_covered_characterization_c4_indep_extend (s : Finset (Fin 4)) (hs : (SimpleGraph.cycleGraph 4).IsIndepSet (s : Set (Fin 4))) (hcard : s.card < 2) : ∃ v : Fin 4, v ∉ s ∧ (SimpleGraph.cycleGraph 4).IsIndepSet ((insert v s : Finset (Fin 4)) : Set (Fin 4)) := by revert s hs hcard decidetheorem not_planar_all_powers_well_covered_characterization_c4_maximal_card (s : Finset (Fin 4)) (hs : Maximal (fun u : Finset (Fin 4) => (SimpleGraph.cycleGraph 4).IsIndepSet (u : Set (Fin 4))) s) : s.card = 2 := by have hle : s.card ≤ 2 := not_planar_all_powers_well_covered_characterization_c4_indep_card_le_two s hs.1 have hge : 2 ≤ s.card := by by_contra! hlt obtain ⟨v, hv_notin, hv_indep⟩ := not_planar_all_powers_well_covered_characterization_c4_indep_extend s hs.1 hlt have hsub : s ≤ insert v s := Finset.subset_insert v s have heq : insert v s ≤ s := hs.2 hv_indep hsub exact hv_notin (heq (Finset.mem_insert_self v s)) omegatheorem not_planar_all_powers_well_covered_characterization_c4_is_well_covered : simple_graph_is_well_covered (SimpleGraph.cycleGraph 4) := by intro s t hs ht rw [not_planar_all_powers_well_covered_characterization_c4_maximal_card s hs, not_planar_all_powers_well_covered_characterization_c4_maximal_card t ht]theorem not_planar_all_powers_well_covered_characterization_c4_all_powers_well_covered : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 4) d) := by have hconn : (SimpleGraph.cycleGraph 4).Connected := @SimpleGraph.cycleGraph_connected 3 exact forall_power_well_covered_of_well_covered_diam_le_two (SimpleGraph.cycleGraph 4) hconn not_planar_all_powers_well_covered_characterization_c4_diam_le_two not_planar_all_powers_well_covered_characterization_c4_is_well_coveredlemma not_planar_all_powers_well_covered_characterization_not_iso_top_c4 : ¬ ∃ k : ℕ, k ≤ 4 ∧ Nonempty (SimpleGraph.cycleGraph 4 ≃g (⊤ : SimpleGraph (Fin k))) := by intro ⟨k, hk, ⟨e⟩⟩ have hcard : Fintype.card (Fin 4) = Fintype.card (Fin k) := Fintype.card_congr e.toEquiv simp only [Fintype.card_fin] at hcard subst hcard have hadj : (⊤ : SimpleGraph (Fin 4)).Adj (e 0) (e 2) := by rw [SimpleGraph.top_adj] intro h have : (0 : Fin 4) = 2 := e.injective h revert this; decide have h_c4 : (SimpleGraph.cycleGraph 4).Adj 0 2 := e.map_adj_iff.mp hadj revert h_c4 decidelemma not_planar_all_powers_well_covered_characterization_not_iso_blowup_c4 : ¬ ∃ a : Fin 5 → ℕ, (∀ i, 0 < a i) ∧ Nonempty (simple_graph_clique_blowup (SimpleGraph.cycleGraph 5) a ≃g SimpleGraph.cycleGraph 4) := by intro ⟨a, ha, ⟨e⟩⟩ have hcard : Fintype.card (Σ i : Fin 5, Fin (a i)) = Fintype.card (Fin 4) := Fintype.card_congr e.toEquiv rw [Fintype.card_sigma] at hcard simp only [Fintype.card_fin] at hcard have hsum : 5 ≤ ∑ i : Fin 5, a i := by have : ∑ i : Fin 5, (1 : ℕ) ≤ ∑ i : Fin 5, a i := Finset.sum_le_sum (fun i _ => ha i) simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, nsmul_eq_mul, mul_one] at this exact this omega/-- Refutation of the OP-161 characterization: not every finite connected planar graph with all powers well-covered is a complete graph of order at most 4 or a clique blow-up of C_5 (C_7 is a counterexample). -/theorem not_planar_all_powers_well_covered_characterization : ¬ (∀ {V : Type} [Fintype V] (G : SimpleGraph V), G.Connected → simple_graph_is_planar G → 2 ≤ Fintype.card V → (∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power G d)) → (∃ k : ℕ, k ≤ 4 ∧ Nonempty (G ≃g (⊤ : SimpleGraph (Fin k)))) ∨ (∃ a : Fin 5 → ℕ, (∀ i, 0 < a i) ∧ Nonempty (simple_graph_clique_blowup (SimpleGraph.cycleGraph 5) a ≃g G))) := by intro h have hconn : (SimpleGraph.cycleGraph 4).Connected := @SimpleGraph.cycleGraph_connected 3 have hplanar : simple_graph_is_planar (SimpleGraph.cycleGraph 4) := not_planar_all_powers_well_covered_characterization_planar_of_card_le_four _ (by decide) have hcard : 2 ≤ Fintype.card (Fin 4) := by decide have hwc := not_planar_all_powers_well_covered_characterization_c4_all_powers_well_covered rcases h (SimpleGraph.cycleGraph 4) hconn hplanar hcard hwc with h1 | h2 · exact not_planar_all_powers_well_covered_characterization_not_iso_top_c4 h1 · exact not_planar_all_powers_well_covered_characterization_not_iso_blowup_c4 h2