cycle_seven_power_two_well_covered
The square of the 7-cycle graph is well-covered: all maximal independent sets have size 2.
Statement
theorem cycle_seven_power_two_well_covered :
simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) 2)- 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
The square of the 7-cycle graph connects vertices at distance at most 2. To prove it is well-covered (all maximal independent sets have the same size), the proof first characterizes distance at most 2 in terms of 1-step and 2-step paths in the cycle, establishing that the power graph equals an explicit graph with decidable adjacency. Because the vertex set Fin 7 is finite, the statement that all maximal independent sets have equal cardinality reduces to an exhaustive finite search, which Lean verifies automatically via the `decide` tactic.
In any simple graph, two vertices have distance at most 2 if and only if they are equal, adjacent, or share a common neighbor.
By taking the contrapositive with `not_iff_not` and pushing negations, having distance at most 2 is equivalent to denying that the distance is strictly greater than 2. The lemma `SimpleGraph.two_lt_edist_iff` directly states that distance greater than 2 means distinct non-adjacent vertices with no common neighbors.
uses
not_iff_not,SimpleGraph.two_lt_edist_iffrw [← not_iff_not] push Not exact SimpleGraph.two_lt_edist_iff
Adjacency in `cycle_seven_power_two_well_covered_G` is symmetric.
Assume u ≠ v are adjacent, so either u is adjacent to v in the 7-cycle C₇ or there is a 2-step path u ∼ w ∼ v. Symmetry of inequality gives v ≠ u. In the first case, v is adjacent to u by symmetry of C₇. In the second case, reversing the two edges yields the path v ∼ w ∼ u via the same intermediate vertex w.
intro u v ⟨hne, h⟩ refine ⟨hne.symm, ?_⟩ rcases h with h1 | ⟨w, hw1, hw2⟩ · left; exact h1.symm · right; exact ⟨w, hw2.symm, hw1.symm⟩⟩
The power graph `simple_graph_power (cycleGraph 7) 2` equals the explicit graph `cycle_seven_power_two_well_covered_G`.
By graph extensionality (`ext u v`), it suffices to check that distinct vertices are adjacent in the power graph if and only if they are adjacent in the explicit graph. Unfolding `simple_graph_power` and simplifying via `Nat.cast_ofNat`, power adjacency means distance at most 2. Applying `cycle_seven_power_two_well_covered_edist_le_two_iff` and unfolding `commonNeighbors` with `mem_commonNeighbors` and `Set.Nonempty` yields the disjunction: equality (ruled out by u ≠ v), adjacency in C₇, or sharing a common neighbor. By symmetry of C₇, having a common neighbor is equivalent to a 2-step path, establishing the two-way implication.
uses
Nat.cast_ofNat,cycle_seven_power_two_well_covered_edist_le_two_iff,mem_commonNeighbors,Set.Nonemptyext u v simp only [simple_graph_power, cycle_seven_power_two_well_covered_G, Nat.cast_ofNat] rw [cycle_seven_power_two_well_covered_edist_le_two_iff] simp only [mem_commonNeighbors, Set.Nonempty] constructor · rintro ⟨hne, rfl | hadj | ⟨w, hw1, hw2⟩⟩ · exact (hne rfl).elim · exact ⟨hne, Or.inl hadj⟩ · exact ⟨hne, Or.inr ⟨w, hw1, hw2.symm⟩⟩ · rintro ⟨hne, hadj | ⟨w, hw1, hw2⟩⟩ · exact ⟨hne, Or.inr (Or.inl hadj)⟩ · exact ⟨hne, Or.inr (Or.inr ⟨w, hw1, hw2.symm⟩)⟩
Adjacency in `cycle_seven_power_two_well_covered_G` is a decidable relation. automation
Adjacency is defined by boolean combinations of equality, cycle adjacency, and an existential quantifier over the finite type Fin 7. Typeclass synthesis (`infer_instance`) automatically derives the decision procedure.
intro u v dsimp [cycle_seven_power_two_well_covered_G] infer_instance
The square of the 7-cycle graph is well-covered. automation
Rewriting with `cycle_seven_power_two_well_covered_eq` substitutes the decidable graph `cycle_seven_power_two_well_covered_G`. Unfolding `simple_graph_is_well_covered` and `Maximal` reduces the theorem to showing that all maximal independent sets in this finite graph have equal cardinality. Because the vertex set Fin 7 is finite and adjacency is decidable, the `decide` tactic checks this property by exhaustive boolean evaluation, verifying that every maximal independent set has size 2.
uses
cycle_seven_power_two_well_covered_eq,Maximalrw [cycle_seven_power_two_well_covered_eq] unfold simple_graph_is_well_covered simp only [Maximal] decide
not_iff_not- Two propositions are equivalent if and only if their negations are equivalent.
SimpleGraph.two_lt_edist_iff- In any simple graph, the distance between two vertices is strictly greater than 2 if and only if the vertices are distinct, non-adjacent, and have no common neighbors.
cycle_seven_power_two_well_covered_edist_le_two_iff- In any simple graph, the distance between two vertices is at most 2 if and only if the vertices are equal, adjacent, or share a common neighbor.
Nat.cast_ofNat- Coercion of a numeral from ℕ into another numeric type (here ℕ∞) preserves its numerical value.
mem_commonNeighbors- A vertex belongs to the set of common neighbors of two vertices if and only if it is adjacent to both.
Set.Nonempty- A set is nonempty if and only if there exists an element belonging to it.
cycle_seven_power_two_well_covered_eq- The square of the 7-cycle graph is equal to the graph whose edges connect distinct vertices at cycle distance 1 or 2.
Maximal- An element x is maximal with respect to a predicate P if P(x) holds and no strictly greater element satisfies P.
- The definition of graph power `simple_graph_power` uses the extended distance metric `edist`, which is defined non-constructively via paths. To make the property checkable by Lean's `decide` tactic, the proof introduces an equivalent graph `cycle_seven_power_two_well_covered_G` with an explicit, decidable adjacency relation (1-step and 2-step paths in the cycle).
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.
open SimpleGraphprivate theorem cycle_seven_power_two_well_covered_edist_le_two_iff {V : Type*} (G : SimpleGraph V) (u v : V) : G.edist u v ≤ (2 : ℕ∞) ↔ u = v ∨ G.Adj u v ∨ (G.commonNeighbors u v).Nonempty := by rw [← not_iff_not] push Not exact SimpleGraph.two_lt_edist_iffprivate def cycle_seven_power_two_well_covered_G : SimpleGraph (Fin 7) where Adj u v := u ≠ v ∧ ((cycleGraph 7).Adj u v ∨ ∃ w : Fin 7, (cycleGraph 7).Adj u w ∧ (cycleGraph 7).Adj w v) symm := ⟨by intro u v ⟨hne, h⟩ refine ⟨hne.symm, ?_⟩ rcases h with h1 | ⟨w, hw1, hw2⟩ · left; exact h1.symm · right; exact ⟨w, hw2.symm, hw1.symm⟩⟩ loopless := ⟨fun u ⟨hne, _⟩ => hne rfl⟩private lemma cycle_seven_power_two_well_covered_eq : simple_graph_power (cycleGraph 7) 2 = cycle_seven_power_two_well_covered_G := by ext u v simp only [simple_graph_power, cycle_seven_power_two_well_covered_G, Nat.cast_ofNat] rw [cycle_seven_power_two_well_covered_edist_le_two_iff] simp only [mem_commonNeighbors, Set.Nonempty] constructor · rintro ⟨hne, rfl | hadj | ⟨w, hw1, hw2⟩⟩ · exact (hne rfl).elim · exact ⟨hne, Or.inl hadj⟩ · exact ⟨hne, Or.inr ⟨w, hw1, hw2.symm⟩⟩ · rintro ⟨hne, hadj | ⟨w, hw1, hw2⟩⟩ · exact ⟨hne, Or.inr (Or.inl hadj)⟩ · exact ⟨hne, Or.inr (Or.inr ⟨w, hw1, hw2.symm⟩)⟩instance cycle_seven_power_two_well_covered_decidableRel : DecidableRel cycle_seven_power_two_well_covered_G.Adj := by intro u v dsimp [cycle_seven_power_two_well_covered_G] infer_instance/-- The square of the 7-cycle graph is well-covered: all maximal independent sets have size 2. -/theorem cycle_seven_power_two_well_covered : simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) 2) := by rw [cycle_seven_power_two_well_covered_eq] unfold simple_graph_is_well_covered simp only [Maximal] decide