Formally, a tree decomposition of a graph is defined as a pair ({X i | i ∈ I}, T = (I, F)) where tree T satisfies all of the following properties.
r Vertex cover: The nodes of the tree T cover all the vertices of G: r Edge cover: Each edge in G is included in some node of T. for all r Running intersection: The nodes of T containing a given vertex of G form a connected subtree.