AFTD Auto-Formalizing Theoretical Domains

cycle_seven_power_two_well_covered

theoremverified

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

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.

  1. 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.

    lines 5–7

    uses not_iff_not, SimpleGraph.two_lt_edist_iff

      rw [← not_iff_not]
      push Not
      exact SimpleGraph.two_lt_edist_iff
  2. 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.

    lines 12–16

        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⟩⟩
  3. 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.

    lines 21–32

    uses Nat.cast_ofNat, cycle_seven_power_two_well_covered_edist_le_two_iff, mem_commonNeighbors, Set.Nonempty

      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⟩)⟩
  4. 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.

    lines 36–38

      intro u v
      dsimp [cycle_seven_power_two_well_covered_G]
      infer_instance
  5. 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.

    lines 43–46

    uses cycle_seven_power_two_well_covered_eq, Maximal

      rw [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.

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

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