AFTD Auto-Formalizing Theoretical Domains

simple_graph_has_equivalence_cover_pullback

theoremverified

Let G and H be simple graphs on arbitrary types V and W, t a natural number, and f an injective map from V to W such that G adjacency is equivalent to H adjacency of the images. If H has an equivalence cover with t layers, then G has an equivalence cover with t layers.

Statement

theorem simple_graph_has_equivalence_cover_pullback
    {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (t : ℕ)
    (f : V → W) (hf : Function.Injective f)
    (hadj : ∀ u v, G.Adj u v ↔ H.Adj (f u) (f v))
    (hcover : simple_graph_has_equivalence_cover H t) :
    simple_graph_has_equivalence_cover G t
Source
arXiv:2610.15635, Proposition 3.2, with induced floor embedding from Lemma 3.1 and cover restriction from Lemma 2.1. This formalizes the published upper bound serving OP-205 / RT-1; no new research result is claimed.
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.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 2

The proof, explained

An equivalence cover of size t on H partitions the vertices in each layer into cliques such that every edge is monochromatic in at least one layer. We pull back each layer's coloring along the injective embedding f : V → W to form an equivalence relation on V, and select a canonical representative d s u for each equivalence class. Because two vertices in V share a representative under d s if and only if their images share a color under c s, the clique and edge-covering conditions on H transfer directly along the embedding to establish that d is an equivalence cover for G.

  1. We unpack the assumed equivalence cover of H into its constituent properties.

    Working classically, we destruct the assumption that H has an equivalence cover of size t to obtain the layer colorings c : Fin t → W → W, the clique condition hc (monochromatic distinct vertices in a layer are adjacent in H), and the edge-covering condition hcov (every edge in H is monochromatic in some layer).

    lines 11–12

      classical
      obtain ⟨c, hc, hcov⟩ := hcover
  2. We define the pulled-back equivalence relations on V and candidate representative maps d s.

    For each layer s, we define the equivalence relation R s on V as the kernel of c s ∘ f, meaning u and v are related if c s (f u) = c s (f v). We then define d s u to be the canonical representative (Quotient.out) of the equivalence class of u under R s.

    lines 13–14

      let R : Fin t → Setoid V := fun s => Setoid.ker (fun u => c s (f u))
      let d : Fin t → V → V := fun s u => (Quotient.mk (R s) u).out
  3. Each representative d s u has the same c s ∘ f value as u.

    By Quotient.mk_out, the representative ⟦u⟧.out is related to u under R s. By definition of the kernel relation R s, this means c s (f (d s u)) = c s (f u).

    lines 15–16

    uses Quotient.mk_out

      have hd (s : Fin t) (u : V) : c s (f (d s u)) = c s (f u) :=
        Quotient.mk_out (s := R s) u
  4. Two vertices in V share a representative under d s if and only if their images under f share a color under c s.

    For the forward direction, if d s u = d s v, applying c s ∘ f via congrArg and chaining with the equality from the previous step yields c s (f u) = c s (f v). For the reverse direction, if c s (f u) = c s (f v), then u and v are related under R s; by Quotient.sound their quotient classes are equal, and applying Quotient.out via congrArg gives d s u = d s v.

    lines 17–22

    uses congrArg, Quotient.sound

      have he (s : Fin t) (u v : V) : d s u = d s v ↔ c s (f u) = c s (f v) := by
        constructor
        · intro h
          exact (hd s u).symm.trans ((congrArg (fun a => c s (f a)) h).trans (hd s v))
        · intro h
          exact congrArg Quotient.out (Quotient.sound (s := R s) h)
  5. It suffices to show that d satisfies the clique condition and covering condition for G.

    We provide d as the witness for the equivalence cover of G, reducing the proof to two obligations: verifying that distinct vertices with identical representatives in a layer are adjacent in G, and that every edge of G is covered in some layer.

    line 23

      refine ⟨d, ?_, ?_⟩
  6. Distinct vertices identified by d s are adjacent in G.

    Suppose u ≠ v and d s u = d s v. By the earlier characterization of d, c s (f u) = c s (f v). Because f is injective and u ≠ v, f u ≠ f v. By the clique condition hc for H, f u and f v are adjacent in H. Since f reflects adjacency via hadj, u and v are adjacent in G.

    lines 24–25

      · intro s u v huv heq
        exact (hadj u v).mpr (hc s (f u) (f v) (fun h => huv (hf h)) ((he s u v).mp heq))
  7. Every edge of G is covered by some layer of d.

    Let u and v be adjacent vertices in G. By hadj, f u and f v are adjacent in H. By the cover property hcov of H, there is a layer s where c s (f u) = c s (f v). By the characterization of d, this is equivalent to d s u = d s v, so layer s covers the edge in G.

    lines 26–28

      · intro u v huv
        obtain ⟨s, hs⟩ := hcov (f u) (f v) ((hadj u v).mp huv)
        exact ⟨s, (he s u v).mpr hs⟩
Quotient.mk_out
The canonical representative of the quotient class of an element is equivalent to the element itself: for any element a and setoid s, ⟦a⟧.out ≈ a.
congrArg
Functions preserve equality: if a₁ = a₂, then g a₁ = g a₂.
Quotient.sound
Equivalent elements produce equal equivalence classes in the quotient: if a ≈ b, then ⟦a⟧ = ⟦b⟧.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_has_equivalence_cover_pullback    {V W : Type*} (G : SimpleGraph V) (H : SimpleGraph W) (t : ℕ)    (f : V → W) (hf : Function.Injective f)    (hadj : ∀ u v, G.Adj u v ↔ H.Adj (f u) (f v))    (hcover : simple_graph_has_equivalence_cover H t) :    simple_graph_has_equivalence_cover G t := by  classical  obtain ⟨c, hc, hcov⟩ := hcover  let R : Fin t → Setoid V := fun s => Setoid.ker (fun u => c s (f u))  let d : Fin t → V → V := fun s u => (Quotient.mk (R s) u).out  have hd (s : Fin t) (u : V) : c s (f (d s u)) = c s (f u) :=    Quotient.mk_out (s := R s) u  have he (s : Fin t) (u v : V) : d s u = d s v ↔ c s (f u) = c s (f v) := by    constructor    · intro h      exact (hd s u).symm.trans ((congrArg (fun a => c s (f a)) h).trans (hd s v))    · intro h      exact congrArg Quotient.out (Quotient.sound (s := R s) h)  refine ⟨d, ?_, ?_⟩  · intro s u v huv heq    exact (hadj u v).mpr (hc s (f u) (f v) (fun h => huv (hf h)) ((he s u v).mp heq))  · intro u v huv    obtain ⟨s, hs⟩ := hcov (f u) (f v) ((hadj u v).mp huv)    exact ⟨s, (he s u v).mpr hs⟩
See it in the graphDiscuss this resultChallenge it