Lesson 4

Here is a graph and one of its tree decompositions. The largest bag has size \(3\), so the width of this decomposition is \(2\).

Notice two things. First, every edge of the graph is covered by at least one bag: for example, the edge \(\{d,h\}\) is covered by the bag \(\{d,g,h\}\). Second, if we follow one fixed vertex, say \(f\), then the bags containing it form a connected part of the decomposition tree.