Lesson 7

A few useful observations are immediate from the definition.

• Every graph on \(n\) vertices has treewidth at most \(n-1\): put all vertices into one bag.


• If \(H\) is a subgraph of \(G\), then \(\operatorname{tw}(H)\le \operatorname{tw}(G)\): use the same bags and delete unnecessary vertices and edges.


• Every clique must be contained in some bag.