Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2021/artificial-intelligence/2/d/solution

A tree decomposition of width has bags
with tree edges , , .
Every graph vertex occurs in a bag and every constraint edge has both endpoints in some bag. The bags containing any fixed vertex form a connected connected subgraph of a tree: occurs in , in , in , and in all four. The remaining vertices occur once. Hence the running-intersection condition holds. The maximum bag size is four, giving width .
Under the stated overlap assumptions, is a four-vertex clique, so the treewidth is at least ; this decomposition attains it. A proof of that lower bound is not needed to use the displayed decomposition.

New to topics? Read the docs here!