cycle_seven_power_ge_three_well_covered
Every power d ≥ 3 of the 7-cycle graph is well-covered: since diam(C_7) = 3 ≤ d, the d-th power is the complete graph K_7 and every maximal independent set has size 1.
Statement
theorem cycle_seven_power_ge_three_well_covered (d : ℕ) (hd : 3 ≤ d) :
simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) d)- Source
- step towards cycle_seven_all_powers_well_covered
- Verified
- 31 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…
- Used by 1
- cycle_seven_all_powers_well_coveredFor every positive integer d, the d-th power of the 7-cycle graph C_7 is well-covered.
The proof, explained
Every power d ≥ 3 of the 7-cycle graph C_7 is well-covered. The proof first shows that the diameter of C_7 is 3: using the triangle inequality and modular arithmetic on ℤ/7ℤ, every pair of distinct vertices is at distance at most 3. Because d ≥ 3, any two distinct vertices are within distance d, which makes the d-th power graph the complete graph K_7. In a complete graph, no two vertices can belong to the same independent set, so every maximal independent set must be a singleton of size 1, proving the graph is well-covered.
Basic arithmetic identities hold in ℤ/7ℤ (Fin 7), and any vertex distinct from u is of the form u ± 1, u ± 2, or u ± 3.
We verify by exhaustive finite evaluation (`decide`) several modular arithmetic identities in ℤ/7ℤ: (u + 1) - u = 1, associativity of adding consecutive units ((u + 1) + 1 = u + 2 and (u + 2) + 1 = u + 3), inverses for subtraction, and the fact that any element v ≠ u must equal u + 1, u + 2, u + 3, u - 1, u - 2, or u - 3.
have hsub_succ : ∀ u : Fin 7, (u + 1) - u = 1 := by decide have hadd2 : ∀ u : Fin 7, (u + 1) + 1 = u + 2 := by decide have hadd3 : ∀ u : Fin 7, (u + 2) + 1 = u + 3 := by decide have hpred1 : ∀ u : Fin 7, (u - 1) + 1 = u := by decide have hpred2 : ∀ u : Fin 7, (u - 2) + 2 = u := by decide have hpred3 : ∀ u : Fin 7, (u - 3) + 3 = u := by decide have hdiff : ∀ u v : Fin 7, u ≠ v → (v = u + 1 ∨ v = u + 2 ∨ v = u + 3 ∨ v = u - 1 ∨ v = u - 2 ∨ v = u - 3) := by decide
For every vertex u in C_7, the vertex u + 1 is adjacent to u, and edist(u, u + 1) = 1.
Two vertices in C_7 are adjacent if their difference modulo 7 is ±1. Since (u + 1) - u = 1, u and u + 1 are adjacent (via `SimpleGraph.cycleGraph_adj` and `Or.inr`). Since adjacent vertices have distance 1 (`SimpleGraph.edist_eq_one_iff_adj.mpr`), the graph distance between u and u + 1 is 1.
uses
SimpleGraph.cycleGraph_adj,Or.inr,SimpleGraph.edist_eq_one_iff_adj.mprhave hadj_succ : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).Adj u (u + 1) := by intro u rw [SimpleGraph.cycleGraph_adj] exact Or.inr (hsub_succ u) have hed1 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 1) = 1 := fun u => SimpleGraph.edist_eq_one_iff_adj.mpr (hadj_succ u)
For every vertex u in C_7, edist(u, u + 2) ≤ 2 and edist(u, u + 3) ≤ 3.
By the triangle inequality (`SimpleGraph.edist_triangle`) through u + 1, the distance from u to u + 2 is bounded by edist(u, u + 1) + edist(u + 1, u + 2) = 1 + 1 = 2. Applying the triangle inequality again through u + 2 and adding the inequalities (`add_le_add`), the distance from u to u + 3 is at most edist(u, u + 2) + edist(u + 2, u + 3) ≤ 2 + 1 = 3.
uses
SimpleGraph.edist_triangle,add_le_addhave hed2 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 2) ≤ 2 := by intro u have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7) (u := u) (v := u + 1) (w := (u + 1) + 1) have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1) ≤ 2 := by calc (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1) ≤ (SimpleGraph.cycleGraph 7).edist u (u + 1) + (SimpleGraph.cycleGraph 7).edist (u + 1) ((u + 1) + 1) := htri _ = 1 + 1 := by rw [hed1 u, hed1 (u + 1)] _ = 2 := by norm_num rw [← hadd2 u] exact ht have hed3 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 3) ≤ 3 := by intro u have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7) (u := u) (v := u + 2) (w := (u + 2) + 1) have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1) ≤ 3 := by calc (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1) ≤ (SimpleGraph.cycleGraph 7).edist u (u + 2) + (SimpleGraph.cycleGraph 7).edist (u + 2) ((u + 2) + 1) := htri _ ≤ 2 + 1 := by apply add_le_add · exact hed2 u · rw [hed1 (u + 2)] _ = 3 := by norm_num rw [← hadd3 u] exact ht
Any two distinct vertices in C_7 are at distance at most 3 from each other.
Given distinct vertices u ≠ v, we case-split on whether v is u + 1, u + 2, u + 3, u - 1, u - 2, or u - 3. The positive shifts follow directly from the bounds 1, 2, 3 ≤ 3. For the negative shifts u - k, by the symmetry of graph distance (`SimpleGraph.edist_comm`), edist(u, u - k) = edist(u - k, u) = edist(u - k, (u - k) + k) ≤ k ≤ 3 (using `le_trans`).
uses
SimpleGraph.edist_comm,le_transhave hdist3 : ∀ u v : Fin 7, u ≠ v → (SimpleGraph.cycleGraph 7).edist u v ≤ 3 := by intro u v hv rcases hdiff u v hv with h | h | h | h | h | h · rw [h, hed1 u]; norm_num · rw [h]; exact le_trans (hed2 u) (by norm_num) · rw [h]; exact hed3 u · rw [h, SimpleGraph.edist_comm] have h' := hed1 (u - 1) rw [hpred1 u] at h' rw [h']; norm_num · rw [h, SimpleGraph.edist_comm] have h' := hed2 (u - 2) rw [hpred2 u] at h' exact le_trans h' (by norm_num) · rw [h, SimpleGraph.edist_comm] have h' := hed3 (u - 3) rw [hpred3 u] at h' exact h'
Any two distinct vertices are adjacent in the power graph C_7^d; that is, C_7^d is the complete graph K_7.
By definition of the graph power, distinct vertices u ≠ v are adjacent in C_7^d if their distance in C_7 is at most d. Since edist(u, v) ≤ 3 and 3 ≤ d, transitivity of inequality (`le_trans`) ensures edist(u, v) ≤ d, so every pair of distinct vertices is adjacent.
uses
le_transhave hadj_complete : ∀ u v : Fin 7, u ≠ v → (simple_graph_power (SimpleGraph.cycleGraph 7) d).Adj u v := by intro u v hv exact ⟨hv, le_trans (hdist3 u v hv) (by exact_mod_cast hd)⟩
Every maximal independent set in C_7^d has cardinality exactly 1.
Let s be a maximal independent set. First, |s| ≤ 1 by `Finset.card_le_one`: if s contained two distinct vertices, they would be adjacent because C_7^d is complete, contradicting independence. Second, s is nonempty: if s were empty, it would be strictly contained in the singleton {0}, which is independent (by `SimpleGraph.isIndepSet_iff`, `Finset.coe_singleton`, and `Set.mem_singleton_iff`), contradicting the maximality of s. Since s is nonempty, |s| ≥ 1 (`Finset.card_pos.mpr`). By antisymmetry (`le_antisymm`), |s| = 1.
uses
Finset.card_le_one,Finset.eq_empty_or_nonempty,Finset.empty_subset,SimpleGraph.isIndepSet_iff,Finset.coe_singleton,Set.mem_singleton_iff,absurd,le_antisymm,Finset.card_pos.mprhave hcard : ∀ s : Finset (Fin 7), Maximal (fun u : Finset (Fin 7) => (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet (↑u)) s → s.card = 1 := by intro s hs obtain ⟨hind, hmax⟩ := hs have hle : s.card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb by_contra hne exact hind ha hb hne (hadj_complete a b hne) have hne : s.Nonempty := by rcases Finset.eq_empty_or_nonempty s with h | h · exfalso have hsub : s ⊆ ({0} : Finset (Fin 7)) := by rw [h]; exact Finset.empty_subset _ have hind0 : (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet (↑({0} : Finset (Fin 7)) : Set (Fin 7)) := by rw [SimpleGraph.isIndepSet_iff] intro a ha b hb hne' rw [Finset.coe_singleton, Set.mem_singleton_iff] at ha hb exact absurd (ha.trans hb.symm) hne' have hle' := hmax hind0 hsub have hmem : (0 : Fin 7) ∈ s := hle' (by simp) rw [h] at hmem simp at hmem · exact h exact le_antisymm hle (Finset.card_pos.mpr hne)
The power graph C_7^d is well-covered.
By definition, a graph is well-covered if all maximal independent sets have the same size. For any maximal independent sets s and t, both have cardinality 1 by the previous step, so |s| = |t| = 1.
intro s t hs ht rw [hcard s hs, hcard t ht]
SimpleGraph.cycleGraph_adj- In the cycle graph on n + 2 vertices, two vertices u and v are adjacent if and only if u - v = 1 or v - u = 1.
Or.inr- Proves a disjunction A ∨ B given a proof of the right-hand disjunct B.
SimpleGraph.edist_eq_one_iff_adj.mpr- If two vertices in a simple graph are adjacent, their extended graph distance is 1.
SimpleGraph.edist_triangle- The triangle inequality for extended graph distance: edist(u, w) ≤ edist(u, v) + edist(v, w).
add_le_add- If a ≤ b and c ≤ d, then a + c ≤ b + d.
le_trans- If a ≤ b and b ≤ c, then a ≤ c (transitivity of order).
SimpleGraph.edist_comm- Extended graph distance is symmetric: edist(u, v) = edist(v, u).
Finset.card_le_one- A finite set s has |s| ≤ 1 if and only if any two elements in s are equal.
Finset.eq_empty_or_nonempty- Every finite set is either empty or nonempty.
Finset.empty_subset- The empty set is a subset of every finite set (∅ ⊆ s).
SimpleGraph.isIndepSet_iff- A vertex subset is an independent set if and only if no two distinct vertices in the set are adjacent.
Finset.coe_singleton- The coercion of a singleton finset {a} to a set is the singleton set {a}.
Set.mem_singleton_iff- An element a belongs to the singleton set {b} if and only if a = b.
absurd- From a proposition and its negation, one can derive any conclusion (principle of explosion).
le_antisymm- If a ≤ b and b ≤ a, then a = b (antisymmetry of order).
Finset.card_pos.mpr- If a finite set is nonempty, its cardinality is strictly positive (at least 1).
- Several elementary modular arithmetic identities on the 7-element ring `Fin 7` (lines 4–11) are discharged automatically by the `decide` tactic via exhaustive evaluation across the 7 elements.
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.
/-- Every power d ≥ 3 of the 7-cycle graph is well-covered: since diam(C_7) = 3 ≤ d, the d-th power is the complete graph K_7 and every maximal independent set has size 1. -/theorem cycle_seven_power_ge_three_well_covered (d : ℕ) (hd : 3 ≤ d) : simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) d) := by have hsub_succ : ∀ u : Fin 7, (u + 1) - u = 1 := by decide have hadd2 : ∀ u : Fin 7, (u + 1) + 1 = u + 2 := by decide have hadd3 : ∀ u : Fin 7, (u + 2) + 1 = u + 3 := by decide have hpred1 : ∀ u : Fin 7, (u - 1) + 1 = u := by decide have hpred2 : ∀ u : Fin 7, (u - 2) + 2 = u := by decide have hpred3 : ∀ u : Fin 7, (u - 3) + 3 = u := by decide have hdiff : ∀ u v : Fin 7, u ≠ v → (v = u + 1 ∨ v = u + 2 ∨ v = u + 3 ∨ v = u - 1 ∨ v = u - 2 ∨ v = u - 3) := by decide have hadj_succ : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).Adj u (u + 1) := by intro u rw [SimpleGraph.cycleGraph_adj] exact Or.inr (hsub_succ u) have hed1 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 1) = 1 := fun u => SimpleGraph.edist_eq_one_iff_adj.mpr (hadj_succ u) have hed2 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 2) ≤ 2 := by intro u have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7) (u := u) (v := u + 1) (w := (u + 1) + 1) have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1) ≤ 2 := by calc (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1) ≤ (SimpleGraph.cycleGraph 7).edist u (u + 1) + (SimpleGraph.cycleGraph 7).edist (u + 1) ((u + 1) + 1) := htri _ = 1 + 1 := by rw [hed1 u, hed1 (u + 1)] _ = 2 := by norm_num rw [← hadd2 u] exact ht have hed3 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 3) ≤ 3 := by intro u have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7) (u := u) (v := u + 2) (w := (u + 2) + 1) have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1) ≤ 3 := by calc (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1) ≤ (SimpleGraph.cycleGraph 7).edist u (u + 2) + (SimpleGraph.cycleGraph 7).edist (u + 2) ((u + 2) + 1) := htri _ ≤ 2 + 1 := by apply add_le_add · exact hed2 u · rw [hed1 (u + 2)] _ = 3 := by norm_num rw [← hadd3 u] exact ht have hdist3 : ∀ u v : Fin 7, u ≠ v → (SimpleGraph.cycleGraph 7).edist u v ≤ 3 := by intro u v hv rcases hdiff u v hv with h | h | h | h | h | h · rw [h, hed1 u]; norm_num · rw [h]; exact le_trans (hed2 u) (by norm_num) · rw [h]; exact hed3 u · rw [h, SimpleGraph.edist_comm] have h' := hed1 (u - 1) rw [hpred1 u] at h' rw [h']; norm_num · rw [h, SimpleGraph.edist_comm] have h' := hed2 (u - 2) rw [hpred2 u] at h' exact le_trans h' (by norm_num) · rw [h, SimpleGraph.edist_comm] have h' := hed3 (u - 3) rw [hpred3 u] at h' exact h' have hadj_complete : ∀ u v : Fin 7, u ≠ v → (simple_graph_power (SimpleGraph.cycleGraph 7) d).Adj u v := by intro u v hv exact ⟨hv, le_trans (hdist3 u v hv) (by exact_mod_cast hd)⟩ have hcard : ∀ s : Finset (Fin 7), Maximal (fun u : Finset (Fin 7) => (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet (↑u)) s → s.card = 1 := by intro s hs obtain ⟨hind, hmax⟩ := hs have hle : s.card ≤ 1 := by rw [Finset.card_le_one] intro a ha b hb by_contra hne exact hind ha hb hne (hadj_complete a b hne) have hne : s.Nonempty := by rcases Finset.eq_empty_or_nonempty s with h | h · exfalso have hsub : s ⊆ ({0} : Finset (Fin 7)) := by rw [h]; exact Finset.empty_subset _ have hind0 : (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet (↑({0} : Finset (Fin 7)) : Set (Fin 7)) := by rw [SimpleGraph.isIndepSet_iff] intro a ha b hb hne' rw [Finset.coe_singleton, Set.mem_singleton_iff] at ha hb exact absurd (ha.trans hb.symm) hne' have hle' := hmax hind0 hsub have hmem : (0 : Fin 7) ∈ s := hle' (by simp) rw [h] at hmem simp at hmem · exact h exact le_antisymm hle (Finset.card_pos.mpr hne) intro s t hs ht rw [hcard s hs, hcard t ht]