Tree decomposition ($(T,(B_t{)}_{t\in V(T)})$)

A tree of bags of graph vertices such that every vertex occurs in a bag, both endpoints of every graph edge occur together in a bag, and the bags containing any fixed vertex form a connected connected subgraph of a tree. Its width is ${\max }_t|B_t|-1$. The connected-occurrence condition lets subproblems agree on shared variables while solving a constraint satisfaction problem; an arbitrary cover of edges by small bags is insufficient.

The minimum width of a tree decomposition. A tree has width at most one, while a clique of $k$ vertices forces width at least $k-1$. Every pair of vertices in the clique shares a bag; their connected bag connected subgraphs of a tree have a common intersection by the Helly property of connected connected subgraphs of a tree, placing the whole clique in one bag. Small treewidth is useful for dynamic programming on finite-domain constraint satisfaction problems.