(related to Definition: Minimal Tree Decomposability)
Let \(G(V,E,\gamma)\) be a finite undirected graph. Then the minimal tree decomposability of \(G\) has the following (trivial) bounds:
\[0\le \tau(G)\le n.\]
The lower bound can be improved, if the graph \(G\) has no loops and the total number \(l\) of components, and the total number \(m_i\) of vertices with multiedges in the \(i\)-th component, \(i=1,\ldots,l\) are known to
\[\sum_{i=1}^1 \max(1,m_i) \le \tau(G)\le n.\]
In particular, if \(G\) is a forest with exactly \(l\) trees, the minimal tree decomposability can be exactly calculated as \[\tau(G)=l.\]
Proofs: 1
