Size of tree decomposition

Question

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.

Answer 1

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$.

Answer 2

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