Lemma 8 Given a CSP P and an assignment x   a , a   dom x , if the induced CSP
is emply after achieving strong (k - )-consistency, then the value a is removed P 
from the domain of x when achieving strong k-consistency on P.

Proof

![0_image_1.png](0_image_1.png)

![0_image_2.png](0_image_2.png)

$${\boldsymbol{t}}$$
$$k=$$
$$\begin{array}{c c c c}{{t}}&{{}}&{{}}&{{}}\\ {{}}&{{t}}&{{}}&{{x}}&{{}}\end{array}\quad a$$

![0_image_0.png](0_image_0.png)

$$I^{\flat}$$

k –
 $$\begin{array}{l l l}C&P&_x&_a\\ &&C&\\ \end{array}$$  $$\begin{array}{l l l}a\\ \hline\end{array}$$  $$\begin{array}{l l l}\mathbf{=}&\mathbf{}&\mathbf{}\\ \hline\end{array}$$
k - t s a t C C C P l T k: 2

![0_image_3.png](0_image_3.png)

h h k-consistent node Definition 9 (k-consistent node) A node t in the search tree is a k if the CSP induced by t is not empty after enforcing strong k-consistency. A node which is not k-consistent is called k-inconsistent.

Lemma 9 If node t is k-consistent, its ancestors are also k-consistent.

Proof t P ι

$$\begin{array}{c}{{t}}\\ {{}}\end{array}$$

![0_image_4.png](0_image_4.png)

t C t P  P i P i l
t l

$$h_{\mathrm{i}}$$

Theorem 10 If MC k visits a node, then its parent is k-consistent. If a node is k-consistent, then MC , visits the node.

Proof

![0_image_5.png](0_image_5.png)

 $\large\begin{matrix}&&&&&&&&&j\\ &t&&&&&j\\ j&&k&&&&&k\\ &P_{\;\;t\;\;}&&x&&t\;x\\ &&&&&&&&\\ &&k&&t&&\blacksquare\\ &&&&&&&&\\ &&&&&&\text{f}\!\!\text{i}\end{matrix}$
l h

![0_image_6.png](0_image_6.png)

P, l P ,,
$$t\qquad\qquad t$$
l

![0_image_7.png](0_image_7.png)

t x 68 k t t