I am confused over a line in the proof of a theorem which is part of some Graph Theory notes I am working through.
The statement of the theorem is as follows:
$tw(G)=min\{\omega(H)-1:$ $H$ is a triangulation of $G$$\}$, where $tw(G)$ is the tree-width of $G$ and $\omega(H)$ is the size of a maximum clique in $H$.
The proof starts by proving the following claim:
G is chordal (triangulated) if and only if it has a tree-decomposition with each bag (part) being a clique.
This part of the proof I understand. The proof then continues as follows:
Let $H$ be a triangulation of $G$. Since $G$ is a subgraph of $H$, any tree-decomposition of $H$ is also a tree-decomposition of $G$, and hence $tw(G) \leq tw(H)$. Since every clique of $H$ is contained in one of the bags of its tree-decomposition, we know that $tw(H) \leq \omega(H)-1$.
And so forth…
Now I understand that any tree-decomposition of $H$ is a tree-decomposition of $G$, since I proved this as an exercise. I therefore understand that $tw(G) \leq tw(H)$. I also understand that every clique of $H$ is contained in one of the bags of its tree-decomposition since I also proved this result as an exercise. But why does that imply that $tw(H) \leq \omega(H)-1$? Surely every tree-composition of $H$ must have a bag that contains the largest clique in $H$, hence the width of any tree-decomposition of $H$ must be at least $\omega(H)-1$, and hence $tw(H) \geq \omega(H)-1$? Am I missing something?
Many thanks
Best Answer
You are right: $tw(H) \geq \omega(H) - 1$. On the other hand, since $H$ is chordal, it has a tree-decomposition where every "bag" is a clique. Such a tree-decomposition must clearly have width $\omega(H) - 1$, which implies $tw(H) \leq \omega(H) - 1$. This shows that for a chordal graph $H$, $tw(H) = \omega(H) - 1$. Without seeing more of the proof it is difficult to say why this is given only as an upper bound; I suppose that the proof doesn't use the fact that equality holds.