has_tree_decomposition_of_width_le
def
A 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 vertex lies in some bag, both ends of every edge lie in a common bag, for every vertex v the nodes whose bags contain v induce a connected subtree, and every bag has at most w + 1 vertices.
Statement
def has_tree_decomposition_of_width_le {α : Type*} (G : SimpleGraph α) (w : ℕ) : Prop
- Defined in
- Short Resolution Refutations for CNFs with Bounded Weighted Incidence Treewidth, arXiv:2610.02047, Sec. 3.2 (tree decompositions; standard textbook notion in graph theory)
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 3
- has_tree_decomposition_single_bagSanity check: every finite graph has a tree decomposition of width at most (number of vertices - 1), the one-node tree whose bag is every…
- graph_treewidthThe treewidth of a graph: the least w such that it has a tree decomposition of width at most w.
- 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
/-- G has a tree decomposition of width at most w. -/ def has_tree_decomposition_of_width_le {α : Type*} (G : SimpleGraph α) (w : ℕ) : Prop := ∃ (N : ℕ) (T : SimpleGraph (Fin N)) (χ : Fin N → Finset α), T.IsTree ∧ (∀ v : α, ∃ t, v ∈ χ t) ∧ (∀ u v : α, G.Adj u v → ∃ t, u ∈ χ t ∧ v ∈ χ t) ∧ (∀ v : α, (T.induce {t | v ∈ χ t}).Connected) ∧ (∀ t, (χ t).card ≤ w + 1)