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
- cnf_incidence_treewidthThe incidence treewidth tw*(F) of a CNF formula F: the treewidth of its incidence graph.
- cnf_incidence_treewidth_le_cardUniversal upper bound: the incidence treewidth of any CNF formula F is at most |vars(F)| + |F|.
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}