Trees · Application: Treewidth (Optional)

Lesson 8

Nikolai Chukhin · Alexander S. Kulikov

Problem. Mark all correct statements.

1 point

  1. If a graph contains \(K_{4}\) as a subgraph, then its treewidth is at least \(3\).

  2. If \(\operatorname{tw}(G)\le k\), then every tree decomposition of \(G\) has width at most \(k\).

  3. Deleting vertices or edges from a graph cannot increase its treewidth.

  4. If a graph is obtained from a forest by adding one new vertex and connecting it to some old vertices, then its treewidth is at most \(2\).