AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number_cycle_power_of_le

theoremverifiedformalization

If 2 ≤ n ≤ 2k + 1 then every two vertices of C_n are at cyclic distance at most k, so C_n^k = K_n and eq(C_n^k) = 1.

Statement

theorem simple_graph_equivalence_covering_number_cycle_power_of_le (n k : ℕ) (hn : 2 ≤ n)
    (hnk : n ≤ 2 * k + 1) :
    simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) = 1
Formalizes
arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Theorem 1.2 (the case n ≤ 2k + 1; the Lean adds n ≥ 2 so that the graph has an edge).
Verified
17 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4

The proof, explained

The proof shows that under the condition n ≤ 2k + 1, the k-th power of the cycle graph C_n^k is the complete graph ⊤ on ℤ/nℤ. For any two distinct vertices u ≠ v, their differences u - v and v - u are nonzero additive inverses whose canonical integer representatives sum to n; since n ≤ 2k + 1, at least one representative is at most k, so every pair of distinct vertices is adjacent in C_n^k. Finally, because n ≥ 2, the vertex set ℤ/nℤ is nontrivial, and the equivalence covering number of the complete graph on a nontrivial vertex set is 1.

  1. To show that the cycle power graph C_n^k equals the complete graph ⊤, it suffices to show that any two distinct vertices u ≠ v in ℤ/nℤ are adjacent in C_n^k.

    We begin establishing the auxiliary identity h_top : simple_graph_cycle_power n k = ⊤. Since n ≥ 2, n is nonzero. By graph extensionality (ext u v), two graphs are equal if they have the same edges. Unfolding the definitions of simple_graph_cycle_power and the complete graph ⊤ (via SimpleGraph.top_adj), this requires showing that u ≠ v ∧ min (u - v).val (v - u).val ≤ k ↔ u ≠ v. The forward implication is immediate, since adjacency in C_n^k already includes the condition u ≠ v.

    lines 4–10

    uses SimpleGraph.top_adj

      have h_top : simple_graph_cycle_power n k = ⊤ := by
        have : NeZero n := ⟨by omega⟩
        ext u v
        simp only [simple_graph_cycle_power, SimpleGraph.top_adj]
        constructor
        · rintro ⟨huv, -⟩
          exact huv
  2. Any two distinct vertices u ≠ v in ℤ/nℤ have cyclic distance at most k, completing the proof that C_n^k = ⊤.

    For the reverse direction, we assume u ≠ v and show min (u - v).val (v - u).val ≤ k. Because u ≠ v, the difference u - v is nonzero by sub_eq_zero.mp. Since v - u = -(u - v) by neg_sub, its canonical integer representative in ℤ/nℤ is n - (u - v).val by ZMod.val_neg_of_ne_zero. Furthermore, (u - v).val < n by ZMod.val_lt. Since (u - v).val and n - (u - v).val sum to n ≤ 2k + 1, linear integer arithmetic (omega) concludes that their minimum is at most k. This finishes the proof that C_n^k = ⊤.

    lines 11–16

    uses sub_eq_zero.mp, neg_sub, ZMod.val_neg_of_ne_zero, ZMod.val_lt

        · intro huv
          refine ⟨huv, ?_⟩
          have : NeZero (u - v) := ⟨fun h => huv (sub_eq_zero.mp h)⟩
          rw [← neg_sub u v, ZMod.val_neg_of_ne_zero (u - v)]
          have hlt := ZMod.val_lt (u - v)
          omega
  3. Since C_n^k is the complete graph on a nontrivial vertex set, its equivalence covering number is 1.

    Rewriting with C_n^k = ⊤, the goal becomes computing the equivalence covering number of the complete graph ⊤ on ℤ/nℤ. Since n ≥ 2, we have 1 < n, which implies that ℤ/nℤ is a nontrivial type (ZMod.nontrivial). Applying simple_graph_equivalence_covering_number_top directly yields that the equivalence covering number is 1.

    lines 17–20

    uses ZMod.nontrivial, simple_graph_equivalence_covering_number_top

      rw [h_top]
      have : Fact (1 < n) := ⟨by omega⟩
      have : Nontrivial (ZMod n) := ZMod.nontrivial n
      exact simple_graph_equivalence_covering_number_top
SimpleGraph.top_adj
Two vertices in the complete graph ⊤ are adjacent if and only if they are distinct.
sub_eq_zero.mp
If a difference a - b is zero, then a = b.
neg_sub
The negation -(a - b) equals b - a.
ZMod.val_neg_of_ne_zero
For a nonzero element a in ℤ/nℤ, the canonical integer representative of -a is n - a.val.
ZMod.val_lt
The canonical integer representative a.val of an element a in ℤ/nℤ is strictly less than n.
ZMod.nontrivial
If n > 1, then ℤ/nℤ has at least two distinct elements (is a nontrivial type).
simple_graph_equivalence_covering_number_top
The equivalence covering number of the complete graph ⊤ on a nontrivial vertex set is 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

theorem simple_graph_equivalence_covering_number_cycle_power_of_le (n k : ℕ) (hn : 2 ≤ n)    (hnk : n ≤ 2 * k + 1) :    simple_graph_equivalence_covering_number (simple_graph_cycle_power n k) = 1 := by  have h_top : simple_graph_cycle_power n k = ⊤ := by    have : NeZero n := ⟨by omega⟩    ext u v    simp only [simple_graph_cycle_power, SimpleGraph.top_adj]    constructor    · rintro ⟨huv, -⟩      exact huv    · intro huv      refine ⟨huv, ?_⟩      have : NeZero (u - v) := ⟨fun h => huv (sub_eq_zero.mp h)⟩      rw [← neg_sub u v, ZMod.val_neg_of_ne_zero (u - v)]      have hlt := ZMod.val_lt (u - v)      omega  rw [h_top]  have : Fact (1 < n) := ⟨by omega⟩  have : Nontrivial (ZMod n) := ZMod.nontrivial n  exact simple_graph_equivalence_covering_number_top
See it in the graphDiscuss this resultChallenge it