AFTD Auto-Formalizing Theoretical Domains

cycle_seven_power_ge_three_well_covered

theoremverified

Every power d ≥ 3 of the 7-cycle graph is well-covered: since diam(C_7) = 3 ≤ d, the d-th power is the complete graph K_7 and every maximal independent set has size 1.

Statement

theorem cycle_seven_power_ge_three_well_covered (d : ℕ) (hd : 3 ≤ d) :
    simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) d)
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

Every power d ≥ 3 of the 7-cycle graph C_7 is well-covered. The proof first shows that the diameter of C_7 is 3: using the triangle inequality and modular arithmetic on ℤ/7ℤ, every pair of distinct vertices is at distance at most 3. Because d ≥ 3, any two distinct vertices are within distance d, which makes the d-th power graph the complete graph K_7. In a complete graph, no two vertices can belong to the same independent set, so every maximal independent set must be a singleton of size 1, proving the graph is well-covered.

  1. Basic arithmetic identities hold in ℤ/7ℤ (Fin 7), and any vertex distinct from u is of the form u ± 1, u ± 2, or u ± 3.

    We verify by exhaustive finite evaluation (`decide`) several modular arithmetic identities in ℤ/7ℤ: (u + 1) - u = 1, associativity of adding consecutive units ((u + 1) + 1 = u + 2 and (u + 2) + 1 = u + 3), inverses for subtraction, and the fact that any element v ≠ u must equal u + 1, u + 2, u + 3, u - 1, u - 2, or u - 3.

    lines 4–11

      have hsub_succ : ∀ u : Fin 7, (u + 1) - u = 1 := by decide
      have hadd2 : ∀ u : Fin 7, (u + 1) + 1 = u + 2 := by decide
      have hadd3 : ∀ u : Fin 7, (u + 2) + 1 = u + 3 := by decide
      have hpred1 : ∀ u : Fin 7, (u - 1) + 1 = u := by decide
      have hpred2 : ∀ u : Fin 7, (u - 2) + 2 = u := by decide
      have hpred3 : ∀ u : Fin 7, (u - 3) + 3 = u := by decide
      have hdiff : ∀ u v : Fin 7, u ≠ v →
          (v = u + 1 ∨ v = u + 2 ∨ v = u + 3 ∨ v = u - 1 ∨ v = u - 2 ∨ v = u - 3) := by decide
  2. For every vertex u in C_7, the vertex u + 1 is adjacent to u, and edist(u, u + 1) = 1.

    Two vertices in C_7 are adjacent if their difference modulo 7 is ±1. Since (u + 1) - u = 1, u and u + 1 are adjacent (via `SimpleGraph.cycleGraph_adj` and `Or.inr`). Since adjacent vertices have distance 1 (`SimpleGraph.edist_eq_one_iff_adj.mpr`), the graph distance between u and u + 1 is 1.

    lines 12–17

    uses SimpleGraph.cycleGraph_adj, Or.inr, SimpleGraph.edist_eq_one_iff_adj.mpr

      have hadj_succ : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).Adj u (u + 1) := by
        intro u
        rw [SimpleGraph.cycleGraph_adj]
        exact Or.inr (hsub_succ u)
      have hed1 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 1) = 1 := fun u =>
        SimpleGraph.edist_eq_one_iff_adj.mpr (hadj_succ u)
  3. For every vertex u in C_7, edist(u, u + 2) ≤ 2 and edist(u, u + 3) ≤ 3.

    By the triangle inequality (`SimpleGraph.edist_triangle`) through u + 1, the distance from u to u + 2 is bounded by edist(u, u + 1) + edist(u + 1, u + 2) = 1 + 1 = 2. Applying the triangle inequality again through u + 2 and adding the inequalities (`add_le_add`), the distance from u to u + 3 is at most edist(u, u + 2) + edist(u + 2, u + 3) ≤ 2 + 1 = 3.

    lines 18–44

    uses SimpleGraph.edist_triangle, add_le_add

      have hed2 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 2) ≤ 2 := by
        intro u
        have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7)
          (u := u) (v := u + 1) (w := (u + 1) + 1)
        have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1) ≤ 2 := by
          calc (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1)
              ≤ (SimpleGraph.cycleGraph 7).edist u (u + 1) +
                  (SimpleGraph.cycleGraph 7).edist (u + 1) ((u + 1) + 1) := htri
            _ = 1 + 1 := by rw [hed1 u, hed1 (u + 1)]
            _ = 2 := by norm_num
        rw [← hadd2 u]
        exact ht
      have hed3 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 3) ≤ 3 := by
        intro u
        have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7)
          (u := u) (v := u + 2) (w := (u + 2) + 1)
        have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1) ≤ 3 := by
          calc (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1)
              ≤ (SimpleGraph.cycleGraph 7).edist u (u + 2) +
                  (SimpleGraph.cycleGraph 7).edist (u + 2) ((u + 2) + 1) := htri
            _ ≤ 2 + 1 := by
                apply add_le_add
                · exact hed2 u
                · rw [hed1 (u + 2)]
            _ = 3 := by norm_num
        rw [← hadd3 u]
        exact ht
  4. Any two distinct vertices in C_7 are at distance at most 3 from each other.

    Given distinct vertices u ≠ v, we case-split on whether v is u + 1, u + 2, u + 3, u - 1, u - 2, or u - 3. The positive shifts follow directly from the bounds 1, 2, 3 ≤ 3. For the negative shifts u - k, by the symmetry of graph distance (`SimpleGraph.edist_comm`), edist(u, u - k) = edist(u - k, u) = edist(u - k, (u - k) + k) ≤ k ≤ 3 (using `le_trans`).

    lines 45–62

    uses SimpleGraph.edist_comm, le_trans

      have hdist3 : ∀ u v : Fin 7, u ≠ v → (SimpleGraph.cycleGraph 7).edist u v ≤ 3 := by
        intro u v hv
        rcases hdiff u v hv with h | h | h | h | h | h
        · rw [h, hed1 u]; norm_num
        · rw [h]; exact le_trans (hed2 u) (by norm_num)
        · rw [h]; exact hed3 u
        · rw [h, SimpleGraph.edist_comm]
          have h' := hed1 (u - 1)
          rw [hpred1 u] at h'
          rw [h']; norm_num
        · rw [h, SimpleGraph.edist_comm]
          have h' := hed2 (u - 2)
          rw [hpred2 u] at h'
          exact le_trans h' (by norm_num)
        · rw [h, SimpleGraph.edist_comm]
          have h' := hed3 (u - 3)
          rw [hpred3 u] at h'
          exact h'
  5. Any two distinct vertices are adjacent in the power graph C_7^d; that is, C_7^d is the complete graph K_7.

    By definition of the graph power, distinct vertices u ≠ v are adjacent in C_7^d if their distance in C_7 is at most d. Since edist(u, v) ≤ 3 and 3 ≤ d, transitivity of inequality (`le_trans`) ensures edist(u, v) ≤ d, so every pair of distinct vertices is adjacent.

    lines 63–66

    uses le_trans

      have hadj_complete : ∀ u v : Fin 7, u ≠ v →
          (simple_graph_power (SimpleGraph.cycleGraph 7) d).Adj u v := by
        intro u v hv
        exact ⟨hv, le_trans (hdist3 u v hv) (by exact_mod_cast hd)⟩
  6. Every maximal independent set in C_7^d has cardinality exactly 1.

    Let s be a maximal independent set. First, |s| ≤ 1 by `Finset.card_le_one`: if s contained two distinct vertices, they would be adjacent because C_7^d is complete, contradicting independence. Second, s is nonempty: if s were empty, it would be strictly contained in the singleton {0}, which is independent (by `SimpleGraph.isIndepSet_iff`, `Finset.coe_singleton`, and `Set.mem_singleton_iff`), contradicting the maximality of s. Since s is nonempty, |s| ≥ 1 (`Finset.card_pos.mpr`). By antisymmetry (`le_antisymm`), |s| = 1.

    lines 67–92

    uses Finset.card_le_one, Finset.eq_empty_or_nonempty, Finset.empty_subset, SimpleGraph.isIndepSet_iff, Finset.coe_singleton, Set.mem_singleton_iff, absurd, le_antisymm, Finset.card_pos.mpr

      have hcard : ∀ s : Finset (Fin 7),
          Maximal (fun u : Finset (Fin 7) =>
            (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet (↑u)) s → s.card = 1 := by
        intro s hs
        obtain ⟨hind, hmax⟩ := hs
        have hle : s.card ≤ 1 := by
          rw [Finset.card_le_one]
          intro a ha b hb
          by_contra hne
          exact hind ha hb hne (hadj_complete a b hne)
        have hne : s.Nonempty := by
          rcases Finset.eq_empty_or_nonempty s with h | h
          · exfalso
            have hsub : s ⊆ ({0} : Finset (Fin 7)) := by rw [h]; exact Finset.empty_subset _
            have hind0 : (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet
                (↑({0} : Finset (Fin 7)) : Set (Fin 7)) := by
              rw [SimpleGraph.isIndepSet_iff]
              intro a ha b hb hne'
              rw [Finset.coe_singleton, Set.mem_singleton_iff] at ha hb
              exact absurd (ha.trans hb.symm) hne'
            have hle' := hmax hind0 hsub
            have hmem : (0 : Fin 7) ∈ s := hle' (by simp)
            rw [h] at hmem
            simp at hmem
          · exact h
        exact le_antisymm hle (Finset.card_pos.mpr hne)
  7. The power graph C_7^d is well-covered.

    By definition, a graph is well-covered if all maximal independent sets have the same size. For any maximal independent sets s and t, both have cardinality 1 by the previous step, so |s| = |t| = 1.

    lines 93–94

      intro s t hs ht
      rw [hcard s hs, hcard t ht]
SimpleGraph.cycleGraph_adj
In the cycle graph on n + 2 vertices, two vertices u and v are adjacent if and only if u - v = 1 or v - u = 1.
Or.inr
Proves a disjunction A ∨ B given a proof of the right-hand disjunct B.
SimpleGraph.edist_eq_one_iff_adj.mpr
If two vertices in a simple graph are adjacent, their extended graph distance is 1.
SimpleGraph.edist_triangle
The triangle inequality for extended graph distance: edist(u, w) ≤ edist(u, v) + edist(v, w).
add_le_add
If a ≤ b and c ≤ d, then a + c ≤ b + d.
le_trans
If a ≤ b and b ≤ c, then a ≤ c (transitivity of order).
SimpleGraph.edist_comm
Extended graph distance is symmetric: edist(u, v) = edist(v, u).
Finset.card_le_one
A finite set s has |s| ≤ 1 if and only if any two elements in s are equal.
Finset.eq_empty_or_nonempty
Every finite set is either empty or nonempty.
Finset.empty_subset
The empty set is a subset of every finite set (∅ ⊆ s).
SimpleGraph.isIndepSet_iff
A vertex subset is an independent set if and only if no two distinct vertices in the set are adjacent.
Finset.coe_singleton
The coercion of a singleton finset {a} to a set is the singleton set {a}.
Set.mem_singleton_iff
An element a belongs to the singleton set {b} if and only if a = b.
absurd
From a proposition and its negation, one can derive any conclusion (principle of explosion).
le_antisymm
If a ≤ b and b ≤ a, then a = b (antisymmetry of order).
Finset.card_pos.mpr
If a finite set is nonempty, its cardinality is strictly positive (at least 1).

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 d ≥ 3 of the 7-cycle graph is well-covered: since diam(C_7) = 3 ≤ d, the d-th power is the complete graph K_7 and every maximal independent set has size 1. -/theorem cycle_seven_power_ge_three_well_covered (d : ℕ) (hd : 3 ≤ d) :    simple_graph_is_well_covered (simple_graph_power (SimpleGraph.cycleGraph 7) d) := by  have hsub_succ : ∀ u : Fin 7, (u + 1) - u = 1 := by decide  have hadd2 : ∀ u : Fin 7, (u + 1) + 1 = u + 2 := by decide  have hadd3 : ∀ u : Fin 7, (u + 2) + 1 = u + 3 := by decide  have hpred1 : ∀ u : Fin 7, (u - 1) + 1 = u := by decide  have hpred2 : ∀ u : Fin 7, (u - 2) + 2 = u := by decide  have hpred3 : ∀ u : Fin 7, (u - 3) + 3 = u := by decide  have hdiff : ∀ u v : Fin 7, u ≠ v →      (v = u + 1 ∨ v = u + 2 ∨ v = u + 3 ∨ v = u - 1 ∨ v = u - 2 ∨ v = u - 3) := by decide  have hadj_succ : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).Adj u (u + 1) := by    intro u    rw [SimpleGraph.cycleGraph_adj]    exact Or.inr (hsub_succ u)  have hed1 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 1) = 1 := fun u =>    SimpleGraph.edist_eq_one_iff_adj.mpr (hadj_succ u)  have hed2 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 2) ≤ 2 := by    intro u    have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7)      (u := u) (v := u + 1) (w := (u + 1) + 1)    have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1) ≤ 2 := by      calc (SimpleGraph.cycleGraph 7).edist u ((u + 1) + 1)          ≤ (SimpleGraph.cycleGraph 7).edist u (u + 1) +              (SimpleGraph.cycleGraph 7).edist (u + 1) ((u + 1) + 1) := htri        _ = 1 + 1 := by rw [hed1 u, hed1 (u + 1)]        _ = 2 := by norm_num    rw [← hadd2 u]    exact ht  have hed3 : ∀ u : Fin 7, (SimpleGraph.cycleGraph 7).edist u (u + 3) ≤ 3 := by    intro u    have htri := SimpleGraph.edist_triangle (G := SimpleGraph.cycleGraph 7)      (u := u) (v := u + 2) (w := (u + 2) + 1)    have ht : (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1) ≤ 3 := by      calc (SimpleGraph.cycleGraph 7).edist u ((u + 2) + 1)          ≤ (SimpleGraph.cycleGraph 7).edist u (u + 2) +              (SimpleGraph.cycleGraph 7).edist (u + 2) ((u + 2) + 1) := htri        _ ≤ 2 + 1 := by            apply add_le_add            · exact hed2 u            · rw [hed1 (u + 2)]        _ = 3 := by norm_num    rw [← hadd3 u]    exact ht  have hdist3 : ∀ u v : Fin 7, u ≠ v → (SimpleGraph.cycleGraph 7).edist u v ≤ 3 := by    intro u v hv    rcases hdiff u v hv with h | h | h | h | h | h    · rw [h, hed1 u]; norm_num    · rw [h]; exact le_trans (hed2 u) (by norm_num)    · rw [h]; exact hed3 u    · rw [h, SimpleGraph.edist_comm]      have h' := hed1 (u - 1)      rw [hpred1 u] at h'      rw [h']; norm_num    · rw [h, SimpleGraph.edist_comm]      have h' := hed2 (u - 2)      rw [hpred2 u] at h'      exact le_trans h' (by norm_num)    · rw [h, SimpleGraph.edist_comm]      have h' := hed3 (u - 3)      rw [hpred3 u] at h'      exact h'  have hadj_complete : ∀ u v : Fin 7, u ≠ v →      (simple_graph_power (SimpleGraph.cycleGraph 7) d).Adj u v := by    intro u v hv    exact ⟨hv, le_trans (hdist3 u v hv) (by exact_mod_cast hd)⟩  have hcard : ∀ s : Finset (Fin 7),      Maximal (fun u : Finset (Fin 7) =>        (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet (↑u)) s → s.card = 1 := by    intro s hs    obtain ⟨hind, hmax⟩ := hs    have hle : s.card ≤ 1 := by      rw [Finset.card_le_one]      intro a ha b hb      by_contra hne      exact hind ha hb hne (hadj_complete a b hne)    have hne : s.Nonempty := by      rcases Finset.eq_empty_or_nonempty s with h | h      · exfalso        have hsub : s ⊆ ({0} : Finset (Fin 7)) := by rw [h]; exact Finset.empty_subset _        have hind0 : (simple_graph_power (SimpleGraph.cycleGraph 7) d).IsIndepSet            (↑({0} : Finset (Fin 7)) : Set (Fin 7)) := by          rw [SimpleGraph.isIndepSet_iff]          intro a ha b hb hne'          rw [Finset.coe_singleton, Set.mem_singleton_iff] at ha hb          exact absurd (ha.trans hb.symm) hne'        have hle' := hmax hind0 hsub        have hmem : (0 : Fin 7) ∈ s := hle' (by simp)        rw [h] at hmem        simp at hmem      · exact h    exact le_antisymm hle (Finset.card_pos.mpr hne)  intro s t hs ht  rw [hcard s hs, hcard t ht]
See it in the graphDiscuss this resultChallenge it