Accordingly, detach the treeτ n fromT , replace it withτ b n and call the new treeT , as demonstrated in Figure 8(b).T is a solution ofÛ , and hence (based on the induction assumption) is a solution of U .
all qeq constraints in U are satisfied inT , which also proves: All qeq constraints in U are satisfied inT .