AFTD Auto-Formalizing Theoretical Domains

edge_list_h_colorable

def

With W : Type implicit, takes, in this order, H : SimpleGraph W, n : ℕ and an edge list es : List (ℕ × ℕ) (edge i : Fin es.length joins es[i].1 and es[i].2), and says the multigraph es on the vertices v < n has an H-coloring: there is f : Fin es.length → H.edgeSet such that for every v : ℕ with v < n there is x : W with the image under (fun i => (f i : Sym2 W)) of the set {i | es[i].1 = v ∨ es[i].2 = v} equal to H.incidenceSet x.

Statement

def edge_list_h_colorable {W : Type} (H : SimpleGraph W) (n : ℕ) (es : List (ℕ × ℕ)) : Prop
Defined in
arXiv:2610.35794 (Computational complexity of the H-coloring problem in cubic graphs), Sec. 1: an H-coloring of a cubic graph G is f : E(G) → E(H) with f(∂_G(v)) = ∂_H(x) for some x, for every vertex v (here H a simple graph, G an edge-list multigraph)
Verified
30 Oct 2026
Axioms
none listed
Used by 3
  • h_coloring_cubic_languageFor a type W (implicit, W : Type) and H : SimpleGraph W, h_coloring_cubic_language H : Language Bool is the set of Bool words w such that…
  • petersen_colorable_of_three_edge_colorableIf es is an edge list with edge_list_connected_cubic n es that has a proper 3-edge-coloring c : Fin es.length → Fin 3 (any two distinct…
  • petersen_coloring_languageThe P10-coloring decision problem as a language over Bool (Language Bool): the set of words w such that there exist n : ℕ and es : List (ℕ…

Read back from the Lean

For a type W, a simple graph H on W, a natural number n, and a list of pairs of natural numbers es, edge_list_h_colorable H n es asserts that there exists a function f : Fin es.length → H.edgeSet such that for every natural number v < n, there exists a vertex x : W such that the image under f (coerced to Sym2 W) of the set of indices i : Fin es.length where es[i].1 = v or es[i].2 = v is equal to the incidence set of x in H (i.e., the set of all edges of H containing x).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An edge-list multigraph has an H-coloring: edges map to edges of H, each vertex star onto a vertex star of H. -/
def edge_list_h_colorable {W : Type} (H : SimpleGraph W) (n : ℕ) (es : List (ℕ × ℕ)) : Prop :=
  ∃ f : Fin es.length → H.edgeSet, ∀ v : ℕ, v < n → ∃ x : W,
    (fun i => (f i : Sym2 W)) '' {i | es[i].1 = v ∨ es[i].2 = v} = H.incidenceSet x
See it in the graphDiscuss this resultChallenge it