AFTD Auto-Formalizing Theoretical Domains

simple_graph_wild_number

def

The wild number wld_γ(G) of an edge-coloured graph is the minimum size of a colour-connecting set of edges.

Statement

noncomputable def simple_graph_wild_number {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) : ℕ
Defined in
arXiv:2610.22142 (Wild number for spanning trees in complete and complete bipartite graphs), Sec. 2 (definition of the wild number wld_γ(G)).
Verified
16 Oct 2026
Axioms
none listed
Built on 1
  • simple_graph_is_color_connectingLet γ be an edge colouring of a graph G. A set W of edges of G is colour-connecting if, for every colour c used by γ, the spanning…
Used by 26

Lean source view module on GitHub

/-- The wild number `wld_γ(G)`: the least size of a finite colour-connecting set (0 if there is none, which cannot happen for a finite connected graph). -/
noncomputable def simple_graph_wild_number {V α : Type*} (G : SimpleGraph V) (γ : G.edgeSet → α) : ℕ :=
  sInf {k | ∃ W : Finset (Sym2 V), W.card = k ∧ simple_graph_is_color_connecting G γ ↑W}
See it in the graphDiscuss this resultChallenge it