cycle_seven_power_one_well_covered
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
- 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
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.
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|$.
uses
simple_graph_power_one,simple_graph_is_well_covered,Maximalrw [simple_graph_power_one, simple_graph_is_well_covered] simp only [Maximal]
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.
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.
- The well-coveredness of the 7-cycle graph is verified by finite exhaustive computation (`decide`) rather than an analytic paper argument, which is feasible because the graph has only 7 vertices and 128 subsets.
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.
/-- 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