verify that the claimed property is maintained after the assignment on and . The assignment on is clearly correct by induction hypothesis. Observe that $B_{i, u}$ contains exactly one arc whose terminal vertex lies in $S'$ for any $S' \in \mathcal{T}_{B_{i, u}}$ since ${G_\ell^{\operatorname{rel}}}$ is a relevant subgraph. We can assume from the induction hypothesis that $D_{i-1}(\mathcal{T} \setminus \mathcal{T}_{B_{i, u}})$ contains exactly one arc that ends inside $S''$ for each $S'' \in \mathcal{T} \setminus \mathcal{T}_{B_{i, u}}$ and no further arc. Thus, the assignment on ensures that the claim is correct.

For the second property, we prove by induction over $i  \in \{ 0, \ldots, n_S \}$ that for any $\mathcal{T} \in {\mathcal{S}_{G,\ell}^{\operatorname{reach}}}(S)$, the cost of $S$ associated with $D_i(\mathcal{T})$ is minimized when $S$ is restricted to the vertices $\{ v_1, \dots, v_i \}$. It holds in the base case $i = 0$ because we have $D_0(\emptyset) = \emptyset$. When $i \ge 1$, we assume from the induction hypothesis that values $\operatorname{Cost}(S, D_{i-1}(\mathcal{T}), {w_\ell^{\operatorname{rel}}})$ are minimum for any $\mathcal{T} \subseteq {\mathcal{S}_{G,\ell}^{\operatorname{reach}}}(S)$. Assume towards a contradiction that there exists an arc set $B'$ that satisfies $\operatorname{Cost}(S, D_{i}(\mathcal{T}_{B'}), {w_\ell^{\operatorname{rel}}}) > \operatorname{Cost}(S, B', {w_\ell^{\operatorname{rel}}})$. Let $B_{i}' \subseteq B'$ denote the set of arcs that 