# Size of tree decomposition

Given a graph $$G$$ with $$n$$ vertices, let $$(X, T)$$ be a tree decomposition of $$G$$ with the smallest width. Is the number of nodes in $$T$$ upper bounded by $$n$$? I have googled it but all materials I found discuss only treewidth.

Not a complete answer, but in T. Kloks Treewidth you have the following lemma:

There always exists a nice tree decomposition of width $$k$$ and with at most $$4n$$ bags.

It is NP-complete to determine the minimum number of bags in a tree decomposition of width $$k$$.

Take any node $$X_1$$ of your tree decomposition $$T$$. It contains at least 2 vertices from $$G$$. Let's call $$T'_1 = \{X_1\}$$, a new tree containing only this node. And $$L_1$$, the cardinality of the subset of $$G$$ it contains, thus $$L_1 \ge 2.$$

Then you add all the other nodes $$X_i$$ of $$T$$, one by one, to grow this new tree incrementing the index $$i$$ of $$T'_i$$ containing $$L_i$$ vertices of $$G$$. The only rule is to pick a node which is connected to $$T'_i$$, it is always possible as $$T$$ is connected.

Thus, the new node $$X_i$$ is connected to $$T'_{i-1}$$ by only one edge (either it would not be a tree anymore). Let's call $$X_j$$, the other node of this edge.

Then $$X_i$$ contains at least one vertex from $$G$$ which is not in $$X_j$$ and not in any other node of $$T'_{i-1}$$, because it would imply to put a new edge and not respect the tree statement. Then $$L_i \ge L_{i-1} + 1$$.

By induction you get $$n \ge L_k \ge 1+k$$, with $$k$$ the number of nodes in $$T$$.

Then the tree decomposition can have at most $$n-1$$ nodes

• The first sentence is incorrect: It contains at least 2 vertices from $G$. A bag can contain one vertex. – Pål GD Apr 17 '19 at 12:25