AFTD Auto-Formalizing Theoretical Domains

cycle_seven_power_one_well_covered

theoremverified

The first power (the graph itself) of the 7-cycle graph is well-covered.

Statement

theorem cycle_seven_power_one_well_covered :
    simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) 1)
Source
step towards cycle_seven_all_powers_well_covered
Verified
31 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…
  • simple_graph_power_oneG^1 = G.
Used by 1

The proof, explained

The theorem states that the first power of the 7-cycle graph $C_7$ is well-covered. The proof reduces the claim from the graph power to $C_7$ itself and unrolls the definition of well-coveredness into an explicit statement that all maximal independent sets have equal cardinality. Since the graph has only 7 vertices, this condition is a finite combinatorial statement that is verified by exhaustive computation.

  1. The goal reduces to showing that every maximal independent set of the 7-cycle graph has the same cardinality.

    Rewriting with `simple_graph_power_one` simplifies the first power of the cycle graph $C_7$ to $C_7$ itself. Expanding the definition of `simple_graph_is_well_covered` and simplifying with `Maximal` expresses the claim explicitly: for any two subsets $s, t \\subseteq \\mathrm{Fin}\\; 7$, if both are independent sets with no strictly larger independent superset, then $|s| = |t|$.

    lines 4–5

    uses simple_graph_power_one, simple_graph_is_well_covered, Maximal

      rw [simple_graph_power_one, simple_graph_is_well_covered]
      simp only [Maximal]
  2. Every maximal independent set of the 7-cycle graph has the same size, so the graph is well-covered. automation

    The vertex set has only 7 vertices, so there are only $2^7 = 128$ candidate subsets. The universal quantification over pairs of maximal independent sets is a decidable predicate on finite sets, which Lean verifies by exhaustive computation.

    line 6

      decide
simple_graph_power_one
The first power of any simple graph G is G itself.
simple_graph_is_well_covered
A simple graph is well-covered if every two maximal independent sets have the same cardinality.
Maximal
An element s is maximal with respect to a predicate P and partial order ≤ if P(s) holds and whenever P(y) and s ≤ y, then y ≤ s.

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

/-- The first power (the graph itself) of the 7-cycle graph is well-covered. -/theorem cycle_seven_power_one_well_covered :    simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) 1) := by  rw [simple_graph_power_one, simple_graph_is_well_covered]  simp only [Maximal]  decide
See it in the graphDiscuss this resultChallenge it