AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_equivalence_cover_mono

theoremverified

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

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.

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

    line 4

      obtain ⟨c, hc, hcov⟩ := h
  2. Extend 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.

    lines 5–6

      refine ⟨fun i => if hi : (i : ℕ) < s then c ⟨i, hi⟩ else id, fun i u v huv h => ?_,
        fun u v huv => ?_⟩
  3. 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.

    lines 7–9

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

    lines 10–11

      · 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

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