cycle_five_all_powers_well_covered
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
- 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…
- 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.
- Used by 1
- cycle_five_has_well_covered_powersThe 5-cycle graph C_5 has the well-covered powers property.
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.
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.
decideThe 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.
uses
cycle_five_all_powers_well_covered_dist_le_two_aux,SimpleGraph.edist_self,SimpleGraph.Walk.cons,SimpleGraph.Walk.nilrcases 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)
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.
uses
SimpleGraph.ediam_le_iff,cycle_five_all_powers_well_covered_edist_le_two,SimpleGraph.diam,ENat.toNat_le_of_le_natCasthave 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
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.
revert s hs decideEvery 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.
revert s hs hcard decideEvery 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.
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_selfhave 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
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|.
uses
cycle_five_all_powers_well_covered_maximal_cardintro 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]
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.
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_coveredhave 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.
- Several auxiliary facts (cycle_five_all_powers_well_covered_dist_le_two_aux, cycle_five_all_powers_well_covered_indep_card_le_two, and cycle_five_all_powers_well_covered_indep_extend) are proved by decide, which evaluates the finite combinatorial properties directly by computational exhaustion over Fin 5 and its powerset.
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.
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