Each bag in T * must have the contents assigned by Algorithm 1 by the first part of Theorem 1.
by induction over nodes n in T * in bottom-up order, with [i, j] the span of n, each quantity b(i, j) at the completion of the inner loop at line 6 can be no larger than the maximum bag size of the subtree of T * rooted at n. the treewidth returned by Algorithm 1 can be no larger than the treewidth of T * .