A tree decomposition of a graph 
consists of a tree 
and a bag 
for each graph
vertex 
of 
. The bags cover 
, each graph
edge of 
has both endpoints in a bag, and the bags containing any fixed graph
vertex of 
induce a connected subtree
of 
(Robertson and Seymour 1984).
A tree decomposition can support efficient computation of properties such as the independence polynomial. It is not unique, and the tree need not be isomorphic to the original graph. Related representations are called clique trees, join trees, and junction trees.
The width is 
, and minimizing this over tree decompositions
gives the treewidth. Measuring the independence
numbers of the bags instead gives the tree-independence
number. Measuring induced matchings incident
with a bag gives induced matching treewidth.
Bulatov, Y. "Tree Decomposition Package."
Jan. 21, 2011.