AFTD Auto-Formalizing Theoretical Domains

not_planar_all_powers_well_covered_characterization

theoremverifiedformalization

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

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

    lines 4–13

    uses Set.disjoint_iff.mp, not_lt_of_ge, Fintype.card_le_of_injective

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

    lines 17–21

    uses not_planar_all_powers_well_covered_characterization_not_minor_of_card_lt

      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; omega
  3. 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`).

    line 26

      decide
  4. The 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.

    lines 30–33

    uses not_planar_all_powers_well_covered_characterization_c4_dist_le_two_aux, SimpleGraph.edist_self

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

    lines 37–41

    uses SimpleGraph.ediam_le_iff, not_planar_all_powers_well_covered_characterization_c4_edist_le_two, ENat.toNat_le_of_le_natCast

      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 hediam
  6. Every independent set in C_4 contains at most 2 vertices. automation

    Verified by exhaustive search over all subsets of Fin 4 using `decide`.

    lines 46–47

      revert s hs
      decide
  7. Any 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`.

    lines 52–53

      revert s hs hcard
      decide
  8. Every 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.

    lines 58–65

    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_self

      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))
      omega
  9. 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|.

    lines 69–71

    uses not_planar_all_powers_well_covered_characterization_c4_maximal_card

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

    lines 75–79

    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_covered

      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_covered
  11. 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`).

    lines 83–94

    uses Fintype.card_congr, Fintype.card_fin, SimpleGraph.top_adj

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

    lines 98–106

    uses Fintype.card_congr, Fintype.card_sigma, Fintype.card_fin, Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, nsmul_eq_mul, mul_one

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

    lines 117–125

    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_c4

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

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

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