simple_graph_has_equivalence_cover_mono
If G is covered by s equivalence subgraphs, it is covered by any larger number t of them (pad with the edgeless equivalence subgraph).
Statement
theorem simple_graph_has_equivalence_cover_mono {V : Type*} (G : SimpleGraph V) {s t : ℕ} (hst : s ≤ t) (h : simple_graph_has_equivalence_cover G s) : simple_graph_has_equivalence_cover G t
- Source
- Sanity lemma for equivalence covers, arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs).
- Verified
- 17 Oct 2026
- Axioms
Quot.soundpropext- Built on 1
- 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…
- Used by 6
- simple_graph_has_equivalence_cover_cycle_power_large_upperFor natural k at least one and n at least max(2k+2,twice the square of k), the k-th cycle power on n vertices has an equivalence cover…
- simple_graph_equivalence_covering_number_cycle_power_three_of_mod_four_eq_twoFor every n ≥ 10 with n ≡ 2 (mod 4), eq(C_n^3) = 4 = 2 + ⌈log₂ 4⌉. This settles the case k = 3 (m = 2) of the open problem: for even n ≥…
- simple_graph_equivalence_covering_number_cycle_power_seven_of_not_dvdFor every n ≥ 98 not divisible by 8, the equivalence covering number of the 7th power of the n-cycle is 5 = 2 + ⌈log₂ 8⌉. This settles the…
- simple_graph_equivalence_covering_number_cycle_power_forty_six_threeeq(C_46^3) = 4: the smallest case of the open problem (k = 3, n = 46 even, 4 ∤ 46, 46 ≥ 45), where the paper only knows eq ∈ {3, 4, 5}.
- simple_graph_has_equivalence_cover_cycle_power_dyadic_upperFor natural k at least one with k+1 equal to2 to the power m and n at least max(2k+2,twice the square of k), the k-th cycle power on n…
- simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapeUnder the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered,…
The proof, explained
To show that an equivalence cover of size s can be extended to size t whenever s ≤ t, we pad the family of s coloring functions with t - s copies of the identity function. The identity function corresponds to the discrete equivalence relation, which identifies no distinct vertices and thus trivially forms an edgeless subgraph of G. The original s functions already cover all edges of G, and since their indices are strictly less than s ≤ t, their edge coverage is preserved in the extended family.
Extract the given equivalence cover of size s.
From the hypothesis that G has an equivalence cover of size s, we obtain a family of coloring functions c indexed by Fin s, the condition hc that any distinct vertices with the same color are adjacent in G, and the condition hcov that every edge in G is monochromatic under at least one coloring in the family.
obtain ⟨c, hc, hcov⟩ := hExtend the family to size t by padding with the identity function, reducing the goal to verifying the two cover conditions.
We define a candidate cover of size t piecewise: for an index i < s, we reuse the original function c_i, while for i ≥ s, we use the identity function id on V. This reduces the goal to showing that each function in the extended family identifies only adjacent vertices, and that every edge of G is still covered.
refine ⟨fun i => if hi : (i : ℕ) < s then c ⟨i, hi⟩ else id, fun i u v huv h => ?_, fun u v huv => ?_⟩
Each function in the extended family satisfies the subgraph condition: distinct vertices with the same value are adjacent.
For any index i in Fin t and distinct vertices u ≠ v with the same value under the i-th function, we split into cases on whether i < s. If i < s, the dependent conditional simplifies via dif_pos to c_i(u) = c_i(v), so u and v are adjacent by the soundness hc of the original cover. If i ≥ s, the conditional simplifies via dif_neg, not_false_eq_true, and id to u = v, which contradicts the hypothesis u ≠ v.
uses
dif_pos,dif_neg,not_false_eq_true,id· by_cases hi : (i : ℕ) < s · simp only [hi, dif_pos] at h; exact hc _ u v huv h · simp only [hi, dif_neg, not_false_eq_true, id] at h; exact absurd h huv
Every edge of G is covered by some function in the extended family.
Given an edge between u and v, the original covering property hcov yields an index j < s such that c_j(u) = c_j(v). Since s ≤ t, linear arithmetic (omega) shows j < t, so j embeds into Fin t. At this index, the condition j < s holds, so the extended function simplifies to c_j and identifies u and v.
· obtain ⟨j, hj⟩ := hcov u v huv exact ⟨⟨j, by omega⟩, by simp [j.2, hj]⟩
dif_pos- A dependent if-then-else expression evaluates to its then-branch when the condition is true.
dif_neg- A dependent if-then-else expression evaluates to its else-branch when the condition is false.
not_false_eq_true- The negation of False is True.
id- The identity function, sending every element to itself.
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_has_equivalence_cover_mono {V : Type*} (G : SimpleGraph V) {s t : ℕ} (hst : s ≤ t) (h : simple_graph_has_equivalence_cover G s) : simple_graph_has_equivalence_cover G t := by obtain ⟨c, hc, hcov⟩ := h refine ⟨fun i => if hi : (i : ℕ) < s then c ⟨i, hi⟩ else id, fun i u v huv h => ?_, fun u v huv => ?_⟩ · by_cases hi : (i : ℕ) < s · simp only [hi, dif_pos] at h; exact hc _ u v huv h · simp only [hi, dif_neg, not_false_eq_true, id] at h; exact absurd h huv · obtain ⟨j, hj⟩ := hcov u v huv exact ⟨⟨j, by omega⟩, by simp [j.2, hj]⟩