Past exam of the computer science course of the University of Oxford / 2021 / Artificial intelligence / 2 / d / Solution

A tree decomposition of width $3$ has bagswith tree edges $K_1{K}_2$, $K_2{K}_3$, $K_2{K}_4$.

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: $B$ occurs in $K_1,K_2$, $G$ in $K_1,K_2,K_3$, $D$ in $K_2,K_3,K_4$, and $E$ in all four. The remaining vertices occur once. Hence the running-intersection condition holds. The maximum bag size is four, giving width $4-1=3$.

Under the stated overlap assumptions, $\{A,B,E,G\}$ is a four-vertex clique, so the treewidth is at least $3$; this decomposition attains it. A proof of that lower bound is not needed to use the displayed decomposition.