AFTD Auto-Formalizing Theoretical Domains

cycle_seven_all_powers_well_covered

theoremverifiedformalization

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
Used by 1

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.

  1. Fix an arbitrary integer $d \ge 1$.

    We introduce the exponent $d$ and the hypothesis $1 \le d$ into the context.

    line 4

      intro d hd
  2. The 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`.

    lines 5–6

    uses cycle_seven_power_one_well_covered

      by_cases h1 : d = 1
      · subst h1; exact cycle_seven_power_one_well_covered
  3. 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`.

    lines 7–8

    uses cycle_seven_power_two_well_covered

      · by_cases h2 : d = 2
        · subst h2; exact cycle_seven_power_two_well_covered
  4. 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`.

    line 9

    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

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