simple_graph_equivalence_covering_number_cycle_power_of_le
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
- simple_graph_cycle_powerThe k-th power C_n^k of the cycle C_n: vertices are the residues mod n, and two distinct vertices are adjacent when their distance along…
- simple_graph_has_equivalence_coverG can be covered by t equivalence subgraphs: there are t spanning subgraphs of G, each a disjoint union of cliques (isolated vertices…
- simple_graph_equivalence_covering_numberThe equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).
- simple_graph_equivalence_covering_number_topSanity check: a complete graph with at least two vertices has equivalence covering number 1.
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.
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.
uses
SimpleGraph.top_adjhave 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
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 = ⊤.
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
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.
uses
ZMod.nontrivial,simple_graph_equivalence_covering_number_toprw [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.
- The proof packages the inequality 1 < n into a Fact instance so that Lean's typeclass resolution can supply it to ZMod.nontrivial.
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.
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