AFTD Auto-Formalizing Theoretical Domains

simple_graph_equivalence_covering_number

def

The equivalence covering number eq(G): the minimum number of equivalence subgraphs of G whose edge sets cover E(G).

Statement

noncomputable def simple_graph_equivalence_covering_number {V : Type*} (G : SimpleGraph V) : ℕ
Defined in
arXiv:2610.15635 (Covering powers of cycles with equivalence subgraphs), Sec. 1 (definition of eq(G)).
Verified
17 Oct 2026
Axioms
none listed
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 14

Lean source view module on GitHub

/-- The equivalence covering number `eq(G)`: the least `t` such that `G` is covered by `t` equivalence subgraphs (0 if there is none, which cannot happen for a finite graph). -/
noncomputable def simple_graph_equivalence_covering_number {V : Type*} (G : SimpleGraph V) : ℕ :=
  sInf {t | simple_graph_has_equivalence_cover G t}
See it in the graphDiscuss this resultChallenge it