= Solution
\b[True in some cases and false in others.] Equality of the <constraint domain> size and <treewidth> does not decide satisfiability.
For an unsatisfiable example, let $D=\{0,1\}$ and impose the three binary <all-different constraints> $X_1\ne X_2$, $X_2\ne X_3$, and $X_3\ne X_1$. The <primal graph> is a triangle, with <treewidth> two. It needs three different values, so no solution exists despite $|D|=\operatorname{tw}(P)=2$.
For a satisfiable example, take four <variables> with the same <constraint domain> and constraints
$$
X_1\ne X_2,\quad X_2\ne X_3,\quad X_3\ne X_4,\quad X_4\ne X_1.
$$
Its <primal graph> is a four-cycle of <treewidth> two: bags $\{1,2,3\}$ and $\{1,3,4\}$ give width two, while width one would require a <forest>. The assignment $(0,1,0,1)$ satisfies all constraints.
$$
\boxed{|D|=\operatorname{tw}(P)\text{ allows both satisfiable and unsatisfiable instances}.}
$$
Back to article page
