cycle_seven_all_powers_well_covered
For every positive integer d, the d-th power of the 7-cycle graph C_7 is well-covered.
Statement
theorem cycle_seven_all_powers_well_covered :
∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) d)- Formalizes
- arXiv:2610.09300 Example 3.8
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- cycle_seven_power_one_well_coveredThe first power (the graph itself) of the 7-cycle graph is well-covered.
- cycle_seven_power_two_well_coveredThe square of the 7-cycle graph is well-covered: all maximal independent sets have size 2.
- cycle_seven_power_ge_three_well_coveredEvery 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…
- Used by 1
- exists_planar_all_powers_well_covered_diam_eq_threeThere exists a finite connected simple planar graph G with at least two vertices whose diameter is exactly 3 and such that every positive…
Read back from the Lean
For every natural number $d \ge 1$, the $d$-th power of the 7-cycle graph $C_7$ (the graph with the same vertices where two distinct vertices are adjacent if and only if their shortest-path distance in $C_7$ is at most $d$) is well-covered: any two maximal independent sets of vertices (maximal with respect to inclusion among independent sets) 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
The proof proceeds by case analysis on the power exponent $d \ge 1$. The cases $d = 1$ and $d = 2$ are dispatched by specific lemmas showing that the 7-cycle $C_7$ and its square $C_7^2$ are well-covered. For all remaining exponents $d \ge 3$, integer arithmetic confirms $d \ge 3$, and the result follows from an auxiliary lemma stating that every power of $C_7$ of degree at least 3 is well-covered.
Fix an arbitrary integer $d \ge 1$.
We introduce the exponent $d$ and the hypothesis $1 \le d$ into the context.
intro d hdThe graph power $C_7^d$ is well-covered when $d = 1$.
We perform a case distinction on whether $d = 1$. In the case $d = 1$, the goal reduces to showing that the first power $C_7^1$ is well-covered, which holds directly by `cycle_seven_power_one_well_covered`.
uses
cycle_seven_power_one_well_coveredby_cases h1 : d = 1 · subst h1; exact cycle_seven_power_one_well_covered
The graph power $C_7^d$ is well-covered when $d = 2$.
Assuming $d \ne 1$, we split on whether $d = 2$. In the case $d = 2$, the goal reduces to showing that the square $C_7^2$ is well-covered, which is supplied directly by `cycle_seven_power_two_well_covered`.
uses
cycle_seven_power_two_well_covered· by_cases h2 : d = 2 · subst h2; exact cycle_seven_power_two_well_covered
The graph power $C_7^d$ is well-covered when $d \ge 3$.
In the remaining branch where $d \ne 1$ and $d \ne 2$, linear integer arithmetic (`omega`) deduces that $d \ge 3$ from $1 \le d$. The result then follows from `cycle_seven_power_ge_three_well_covered`.
uses
cycle_seven_power_ge_three_well_covered· exact cycle_seven_power_ge_three_well_covered d (by omega)
cycle_seven_power_one_well_covered- The first power of the 7-cycle graph $C_7$ (that is, $C_7$ itself) is well-covered.
cycle_seven_power_two_well_covered- The second power (square) of the 7-cycle graph $C_7$ is well-covered.
cycle_seven_power_ge_three_well_covered- For every integer $d \ge 3$, the $d$-th power of the 7-cycle graph $C_7$ 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
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 of the 7-cycle graph C_7 is well-covered. -/theorem cycle_seven_all_powers_well_covered : ∀ d : ℕ, 1 ≤ d → simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) d) := by intro d hd by_cases h1 : d = 1 · subst h1; exact cycle_seven_power_one_well_covered · by_cases h2 : d = 2 · subst h2; exact cycle_seven_power_two_well_covered · exact cycle_seven_power_ge_three_well_covered d (by omega)