Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 3 / b / ii / Solution

The constraint hypergraph has one vertex for each of $X_1,\dots ,X_9$ and one hypergraph edge for each constraint scope:Here $i$ abbreviates $X_i$. These five scopes follow the corrected source.^[ref] The diagram uses the incidence representation: round nodes are the original variables, square nodes represent hypergraph edges, and a joining line means that the variable belongs to that constraint scope. The square nodes are not extra variables of $P$.

In particular, the central pattern involving $X_2,X_4,X_5$ forms a cycle through three constraint scopes; the scopes cannot themselves simply be joined into a valid tree decomposition without an additional bag.