r k k Theorem 5 BJ k visits all the nodes that BJ k visits.

4.2 Maintaining Strong k -consistency (MC k )
h k h h h induced h h Definition 7 (induced CSP) Given a consistent partial solution t of a CSP P, the CSP
induced by t, denoted by P t, has all the variables in P except those instantiated by t, the domain of each variable is the same as in P, and for each constraint C in P where vars C  Q vars t there is a constraint C
Example 3 Consider the graph coloring problem and the corresponding CSP shown in Figure 3. The original CSP has four variables, x , . . , x , where x , x , x , x r, , and r , and five binary constraints, x  / x , x  / x , x  / x  and x  / x .

x Given a partial solution to a x x and x , and the unary and binary constraints shown in Figure 4.

l a h