the base case $i = 0$ because we have $D_0(\emptyset) = \emptyset$. When $i \ge 1$, since ${G_\ell^{\operatorname{rel}}}$ is a relevant subgraph (see \[def:rel\]), it follows that the set $\{ v_i u \in A({G_\ell^{\operatorname{rel}}}) \mid u \not\in S, S_u \not\in \mathcal{T}_{B_{i - 1}} \}$ on contains exactly one arc whose terminal vertex lies in $S'$ for any $S' \in \mathcal{T}_{B_i} \setminus \mathcal{T}_{B_{i-1}}$. Since the claim holds for $i - 1$ by induction hypothesis, $B_i$ contains exactly one arc that ends inside $S'$ for each $S' \in \mathcal{T}_{B_i}$ and no other arc. In , the algorithm computes from this set $B_i$ of arcs all arcs that end in $\mathcal{T}$ and assigns this to $D_i(\mathcal{T})$. Hence $D_i(\mathcal{T})$ contains exactly one arc for each $S' \in \mathcal{T}$ and thus the the claim holds for $i$ as well.

We now show—again by induction—that the claim holds after the update phase. Again the claim clearly holds for the base case $i = 0$. When $i \ge 1$, note that each iteration step () corresponds to the case in which the cost for $v_i$ is exactly $w(v_i u)$. The algorithm finds the set $B_{i, u}$ of arcs that $v_i$ can cover with cost $w(v_i u)$. We 