AFTD Auto-Formalizing Theoretical Domains

graph_treewidth

def

The treewidth of a graph: the least w such that it has a tree decomposition of width at most w.

Statement

noncomputable def graph_treewidth {α : Type*} (G : SimpleGraph α) : ℕ
Defined in
Short Resolution Refutations for CNFs with Bounded Weighted Incidence Treewidth, arXiv:2610.02047, Sec. 3.2 (treewidth)
Verified
06 Oct 2026
Axioms
none listed
Built on 1
  • has_tree_decomposition_of_width_leA graph G has a tree decomposition of width at most w: a finite tree T and bags chi(t), subsets of the vertices of G, such that every…
Used by 2

Lean source view module on GitHub

/-- The treewidth of a graph: the least width of a tree decomposition. -/
noncomputable def graph_treewidth {α : Type*} (G : SimpleGraph α) : ℕ :=
  sInf {w | has_tree_decomposition_of_width_le G w}
See it in the graphDiscuss this resultChallenge it