simple_graph_has_equivalence_cover_pullback
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
- simple_graph_equivalence_covering_number_cycle_power_large_upperFor every natural k at least one and natural n at least max(2*k+2, twice the square of k), the equivalence covering number of the k-th…
- 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…
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.
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).
classical obtain ⟨c, hc, hcov⟩ := hcoverWe 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.
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
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).
uses
Quotient.mk_outhave hd (s : Fin t) (u : V) : c s (f (d s u)) = c s (f u) := Quotient.mk_out (s := R s) uTwo 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.
uses
congrArg,Quotient.soundhave 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)
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.
refine ⟨d, ?_, ?_⟩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.
· 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))
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.
· 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⟧.
- While on paper an equivalence cover is simply a family of equivalence relations, Lean formalizes each layer as an endomap c s : V → V whose fibers form the equivalence classes. Because pulling back c s along f gives a map from V to W rather than V to V, the proof uses classical choice (via Quotient.out) to pick a representative in V for each fiber, constructing an endomap d s : V → V with the desired level sets.
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.
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⟩