AFTD Auto-Formalizing Theoretical Domains

cycle_five_all_powers_well_covered

theoremverifiedformalization

For every positive integer d, the d-th power of the 5-cycle graph C_5 is well-covered.

Statement

theorem cycle_five_all_powers_well_covered :
    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 5) d)
Formalizes
arXiv:2610.09300 Example 3.7
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

For every natural number $d \ge 1$, the $d$-th power of the 5-cycle graph SimpleGraph.cycleGraph 5 is well-covered; that is, every two maximal independent sets of vertices (as finite sets of vertices in ZMod 5) in the graph power 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

To prove that every positive power of the 5-cycle graph C_5 is well-covered, the proof relies on a general theorem establishing that any finite connected graph with diameter at most 2 that is well-covered has all its powers well-covered. Connectedness of C_5 is standard, and finite case exhaustion confirms that any two vertices are at distance at most 2, bounding the diameter by 2. Finally, exhaustive search demonstrates that every maximal independent set in C_5 has cardinality 2, proving that C_5 is well-covered.

  1. Any two vertices in C_5 are equal, adjacent, or share a common neighbor.

    Because C_5 has only 5 vertices, the disjunction is verified for all 25 pairs of vertices by computational exhaustion using decide.

    line 4

      decide
  2. The extended distance between any two vertices in C_5 is at most 2.

    We case split on the relationship between u and v using cycle_five_all_powers_well_covered_dist_le_two_aux: if u = v, the distance is 0 by SimpleGraph.edist_self; if u is adjacent to v, the walk of length 1 constructed with SimpleGraph.Walk.cons and SimpleGraph.Walk.nil bounds the distance by 1 ≤ 2; if u and v share a neighbor w, the walk of length 2 through w bounds the distance by 2 ≤ 2.

    lines 8–11

    uses cycle_five_all_powers_well_covered_dist_le_two_aux, SimpleGraph.edist_self, SimpleGraph.Walk.cons, SimpleGraph.Walk.nil

      rcases cycle_five_all_powers_well_covered_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)
  3. The diameter of C_5 is at most 2.

    By SimpleGraph.ediam_le_iff and the fact that all pairwise distances are at most 2 (cycle_five_all_powers_well_covered_edist_le_two), the extended diameter is at most 2. Rewriting the definition of diam using SimpleGraph.diam and applying ENat.toNat_le_of_le_natCast converts this bound to the diameter as a natural number.

    lines 15–19

    uses SimpleGraph.ediam_le_iff, cycle_five_all_powers_well_covered_edist_le_two, SimpleGraph.diam, ENat.toNat_le_of_le_natCast

      have hediam : (SimpleGraph.cycleGraph 5).ediam ≤ 2 := by
        rw [SimpleGraph.ediam_le_iff]
        exact cycle_five_all_powers_well_covered_edist_le_two
      rw [SimpleGraph.diam]
      exact ENat.toNat_le_of_le_natCast hediam
  4. Every independent set in C_5 has cardinality at most 2.

    Reverting the set and the independence hypothesis reduces this to a decidable property over all 32 subsets of Fin 5, which decide checks exhaustively.

    lines 24–25

      revert s hs
      decide
  5. Every independent set in C_5 with fewer than 2 vertices can be extended by adding another vertex.

    Reverting the hypotheses leaves a finite combinatorial statement about subsets of size 0 and 1 in Fin 5, which decide verifies by testing all cases.

    lines 30–31

      revert s hs hcard
      decide
  6. Every maximal independent set in C_5 has cardinality exactly 2.

    Let s be a maximal independent set. Its cardinality is at most 2 by cycle_five_all_powers_well_covered_indep_card_le_two. If its cardinality were strictly less than 2, cycle_five_all_powers_well_covered_indep_extend would provide a vertex v ∉ s such that s ∪ {v} is independent. By Finset.subset_insert and maximality, s ∪ {v} ⊆ s, which by Finset.mem_insert_self implies v ∈ s, a contradiction. Thus 2 ≤ |s|, and linear arithmetic (omega) concludes |s| = 2.

    lines 36–43

    uses cycle_five_all_powers_well_covered_indep_card_le_two, cycle_five_all_powers_well_covered_indep_extend, Finset.subset_insert, Finset.mem_insert_self

      have hle : s.card ≤ 2 := cycle_five_all_powers_well_covered_indep_card_le_two s hs.1
      have hge : 2 ≤ s.card := by
        by_contra! hlt
        obtain ⟨v, hv_notin, hv_indep⟩ := cycle_five_all_powers_well_covered_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
  7. C_5 is well-covered.

    For any two maximal independent sets s and t, cycle_five_all_powers_well_covered_maximal_card shows |s| = 2 and |t| = 2, so |s| = |t|.

    lines 47–49

    uses cycle_five_all_powers_well_covered_maximal_card

      intro s t hs ht
      rw [cycle_five_all_powers_well_covered_maximal_card s hs,
          cycle_five_all_powers_well_covered_maximal_card t ht]
  8. For every integer d ≥ 1, the d-th power graph of C_5 is well-covered.

    The 5-cycle graph is connected by SimpleGraph.cycleGraph_connected. Applying the general theorem forall_power_well_covered_of_well_covered_diam_le_two with connectedness, the diameter bound cycle_five_all_powers_well_covered_diam_le_two, and well-coveredness cycle_five_all_powers_well_covered_is_well_covered proves the theorem.

    lines 54–58

    uses SimpleGraph.cycleGraph_connected, forall_power_well_covered_of_well_covered_diam_le_two, cycle_five_all_powers_well_covered_diam_le_two, cycle_five_all_powers_well_covered_is_well_covered

      have hconn : (SimpleGraph.cycleGraph 5).Connected := @SimpleGraph.cycleGraph_connected 4
      exact forall_power_well_covered_of_well_covered_diam_le_two
        (SimpleGraph.cycleGraph 5) hconn
        cycle_five_all_powers_well_covered_diam_le_two
        cycle_five_all_powers_well_covered_is_well_covered
cycle_five_all_powers_well_covered_dist_le_two_aux
Any two vertices in the 5-cycle graph C_5 are equal, adjacent, or share a common neighbor.
cycle_five_all_powers_well_covered_edist_le_two
The extended distance between any two vertices in C_5 is at most 2.
cycle_five_all_powers_well_covered_diam_le_two
The diameter of C_5 is at most 2.
cycle_five_all_powers_well_covered_indep_card_le_two
Every independent set in C_5 has cardinality at most 2.
cycle_five_all_powers_well_covered_indep_extend
Every independent set in C_5 of cardinality strictly less than 2 can be extended by adding another vertex.
cycle_five_all_powers_well_covered_maximal_card
Every maximal independent set in C_5 has cardinality exactly 2.
cycle_five_all_powers_well_covered_is_well_covered
The 5-cycle graph C_5 is well-covered.
SimpleGraph.edist_self
The extended distance from any vertex to itself in a graph is 0.
SimpleGraph.Walk.cons
Prepends an edge from u to v to a walk from v to w, producing a walk from u to w.
SimpleGraph.Walk.nil
The empty walk of length 0 from a vertex to itself.
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.
SimpleGraph.diam
The diameter of a graph as a natural number, defined as the toNat projection of its extended diameter.
ENat.toNat_le_of_le_natCast
If an extended natural number m is at most a natural number n, then m.toNat is at most n.
Finset.subset_insert
A finite set s is a subset of the set obtained by inserting an element a into s.
Finset.mem_insert_self
An element a belongs to the set obtained by inserting a into s.
SimpleGraph.cycleGraph_connected
The cycle graph on n + 1 vertices is connected.
forall_power_well_covered_of_well_covered_diam_le_two
If a finite connected graph G has diameter at most 2 and is well-covered, then every power graph G^d for d ≥ 1 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

theorem cycle_five_all_powers_well_covered_dist_le_two_aux :    ∀ u v : Fin 5, u = v ∨ (SimpleGraph.cycleGraph 5).Adj u v ∨      ∃ w : Fin 5, (SimpleGraph.cycleGraph 5).Adj u w ∧ (SimpleGraph.cycleGraph 5).Adj w v := by  decidetheorem cycle_five_all_powers_well_covered_edist_le_two (u v : Fin 5) :    (SimpleGraph.cycleGraph 5).edist u v ≤ 2 := by  rcases cycle_five_all_powers_well_covered_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 cycle_five_all_powers_well_covered_diam_le_two :    (SimpleGraph.cycleGraph 5).diam ≤ 2 := by  have hediam : (SimpleGraph.cycleGraph 5).ediam ≤ 2 := by    rw [SimpleGraph.ediam_le_iff]    exact cycle_five_all_powers_well_covered_edist_le_two  rw [SimpleGraph.diam]  exact ENat.toNat_le_of_le_natCast hediamtheorem cycle_five_all_powers_well_covered_indep_card_le_two (s : Finset (Fin 5))    (hs : (SimpleGraph.cycleGraph 5).IsIndepSet (s : Set (Fin 5))) :    s.card ≤ 2 := by  revert s hs  decidetheorem cycle_five_all_powers_well_covered_indep_extend (s : Finset (Fin 5))    (hs : (SimpleGraph.cycleGraph 5).IsIndepSet (s : Set (Fin 5))) (hcard : s.card < 2) :    ∃ v : Fin 5, v ∉ s ∧ (SimpleGraph.cycleGraph 5).IsIndepSet ((insert v s : Finset (Fin 5)) : Set (Fin 5)) := by  revert s hs hcard  decidetheorem cycle_five_all_powers_well_covered_maximal_card (s : Finset (Fin 5))    (hs : Maximal (fun u : Finset (Fin 5) => (SimpleGraph.cycleGraph 5).IsIndepSet (u : Set (Fin 5))) s) :    s.card = 2 := by  have hle : s.card ≤ 2 := cycle_five_all_powers_well_covered_indep_card_le_two s hs.1  have hge : 2 ≤ s.card := by    by_contra! hlt    obtain ⟨v, hv_notin, hv_indep⟩ := cycle_five_all_powers_well_covered_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 cycle_five_all_powers_well_covered_is_well_covered :    simple_graph_is_well_covered (SimpleGraph.cycleGraph 5) := by  intro s t hs ht  rw [cycle_five_all_powers_well_covered_maximal_card s hs,      cycle_five_all_powers_well_covered_maximal_card t ht]/-- Every power of the 5-cycle graph C_5 is well-covered. -/theorem cycle_five_all_powers_well_covered :    ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 5) d) := by  have hconn : (SimpleGraph.cycleGraph 5).Connected := @SimpleGraph.cycleGraph_connected 4  exact forall_power_well_covered_of_well_covered_diam_le_two    (SimpleGraph.cycleGraph 5) hconn    cycle_five_all_powers_well_covered_diam_le_two    cycle_five_all_powers_well_covered_is_well_covered
See it in the graphDiscuss this resultChallenge it