Theorem 6 Enforcing BC on i ∈ S → Xi ∈ T , and Xi ∈ T → i ∈ S for all i ∈ [1..n]
achieves BC on Roots([X1, .., Xn]**, S, T** ).

Proof. Soundness. **Immediate.** Completeness. The proof follows the same structure as that in Theorem 5. We relax the properties P1–P4 into properties P1'–P4'.

P1' if [min(Xi), max(Xi)] ⊆ lb(T **) then** i ∈ lb(S)
P2' if [min(Xi), max(Xi)] ∩ ub(T ) = ∅ **then** i 6∈ ub(S) P3' if i ∈ lb(S) then the bounds of Xi **are included in** ub(T ) P4' if i /∈ ub(S) then the bounds of Xi **are outside** lb(T )
Let us prove that lb(T ) and ub(T ) are tight. Let o be the total ordering on D = Si D(Xi)∪ub(T ). Build the tuples σ and τ as follows: For each v ∈ lb(T **): put** v in σ[T ]
and τ[T ]. For each v ∈ ub(T ) \ lb(T ), following o, do: put v in σ[T ] or τ[T **] alternately.** For each i ∈ lb(S), P3' guarantees that both min(Xi) and max(Xi) are in ub(T **). By** construction of σ[T ] (and τ[T ]) with alternation of values, if min(Xi) 6= max(Xi**), we**
are sure that there exists a value in σ[T ] (in τ[T ]) between min(Xi) and max(Xi**). In**
the case |D(Xi)| = 1, P5 guarantees that the only value is in σ[T ] (in τ[T **]). Thus, we** assign Xiin σ (in τ) with such a value in σ[T ] (in τ[T ]). For each i /∈ ub(S**), we assign** Xiin σ with a value in [min(Xi), max(Xi)]\σ[T ] (the same for τ**). We know that such a** value exists with the same reasoning as for i ∈ lb(S**) on alternation of values, and thanks**
to P4' and P6. We complete σ and τ by building σ[S] and τ[S**] consistently with the**
assignments of Xi and T . The resulting tuples satisfy Roots**. From this we deduce that**
lb(T ) and ub(T ) are BC as all values in ub(T ) \ lb(T ) are either in σ or in τ**, but not**
both.

We show that the Xi are BC. Take any Xi and its lower bound min(Xi**). If** i ∈ lb(S)
we know that min(Xi) is in T either in σ or in τ **thanks to P3' and by construction of** σ and τ. We assign min(Xi) to Xi**in the relevant tuple. This remains a solution of**
Roots. If i /∈ ub(S), we know that min(Xi) is outside T either in σ or in τ **thanks to**
P4' and by construction of σ and τ. We assign min(Xi) to Xi**in the relevant tuple.**
This remains a solution of Roots. If i ∈ ub(S) \ lb(S), assign Xi to min(Xi) in σ**. If**
min(Xi) ∈/ σ[T ], remove i from σ[S] else add i to σ[S**]. The tuple obtained is a solution**
of Roots using the lower bound of Xi**. By the same reasoning, we show that the upper**
bound of Xiis BC also, and therefore, all Xi**'s are BC.**
We prove that lb(S) and ub(S**) are BC with similar proofs. Let us show that** ub(S)
is BC. Take any Xi with i ∈ ub(S) and i /∈ σ[S]. Since Xi **was assigned any value from** [min(Xi), max(Xi)] when σ was built, and since we know that [min(Xi)**, max**(Xi)] ∩ ub(T ) 6= ∅ thanks to P2', we can modify σ by assigning Xi a value in ub(T **), putting the**
value in T if not already there, and adding i into S. The tuple obtained satisfies **Roots**.

So ub(S**) is BC.**
There remains to show that lb(S**) is BC. Thanks to P1', we know that values** i ∈
ub(S)\lb(S) are such that [min(Xi), max(Xi)]\lb(T ) 6= ∅. Take v ∈ [min(Xi)**, max**(Xi)]\ lb(T ). Thus, either σ or τ is such that v /∈ T **. Take the corresponding tuple, assign** Xi to v and remove i from S. The modified tuple is still a solution of Roots and lb(S**) is**
BC. ✷