Since we started from a graph that is a tree, the number of CCs in the final sub-graph is exactly $n-\left|S\right|$ , for any $S\subseteq E\left(G\right)$ . Let $S^{*}$ be some optimal solution. It left to show that the sub-graph $H^{*}=\left(V\left(G\right),S^{*}\right)$ has exactly $k$ connected components:

Assume that there are less than $k$ , then we must have two terminals which live in the same CC - invalidating the solution $S^{*}$ . If we assume that there are more than $k$ CCs, then we must have a connected component without a master, so we can safely connect it to some other CC with some edge $e$ that is not in $S^{*}$ (and such edge exists since $G$ is connected). That way, we get a new valid solution with greater weight than the weight of $S^{*}$ which is a contradiction.

Similarly, we prove that $S_{n-1}$ has $k$ CCs: If it has less than $k$ , there must be two terminals in the same CCs, and that contradicts the correctness of $S_{n-1}$ . If it has more than $k$ CCs after $n-1$ iterations, there must be a CC without a master, so we may connect it with some edge, let it be $e_{i}$ , to other CC without invalidating the solution. But that $e_{i}$ wasn’t picked when the algorithm considered it - meaning that it could cause a violation in the sub-graph of the $i$ th iteration, and since that sub-graph is contained in the sub-graph of the last iteration then we can’t add $e_{i}$ to our solution - a contradiction.

For $i=0$ we have $S_{0}=\emptyset$ thus $\mathcal{X}_{0}=\mathcal{X}$ which is not empty. Assume toward contradiction that the claim is false, and let $i$ be the smallest such that $\mathcal{X}_{i}=\emptyset$ , so we know that $\mathcal{X}_{i-1}$ is not empty, and hence $S_{i-1}\ne S_{i}$ . In other words, during the $i$ th iteration, the algorithm added the edge $e_{i}=\left\{ v,u\right\}$ to $S_{i-1}$ , causing $\mathcal{X}_{i}$ to be empty.

Fix some $S^{*}\in\mathcal{X}_{i-1}$ . Denote $H_{i-1}=\left(V\left(G\right),S_{i-1}\right)$ and $H^{*}=\left(V\left(G\right),S^{*}\right)$ the subgraphs of $G$ . From the update rule of the algorithm, at least one of $\left\{ u,v\right\}$ is not dominated by a master over $H_{i-1}$ , w.l.o.g assume it is $u$ . Let $r\in T$ be the master that dominates $u$ over $H^{*}$ , and consider the path connecting $r\rightsquigarrow u$ , note that any edge along that path belongs to $S^{*}$ . Since the path does not exists in $H_{n-1}$ and in particular in $H_{i-1}$ , there is at least one edge that is part of the path and not in $S_{i-1}$ , let $e_{j}$ be such one with minimum weight.

Observe that it is impossible that $w\left(e_{j}\right)>w\left(e_{i}\right)$ because it means that the algorithm already rejected $e_{j}$ on the $j$ th iteration and since it was a violation for $H_{j}$ and $H_{j}\subset H_{i-1}$ then it is also a violation for $H_{i-1}$ therefore $e_{j}$ does not belongs to any optimal solution in $\mathcal{X}_{i-1}$ , in contradiction that $e_{j}\in S^{*}\in\mathcal{X}_{i-1}$ .

So suppose $w\left(e_{j}\right)\le w\left(e_{i}\right)$ . Note that in the sub-graph $H^{*}$ induced by $S^{*}$ , $v$ must be dominated my some terminal $t\in T$ . Because $H^{*}$ is a sub-graph of a tree, if $t=r$ then we can close a cycle by adding $e_{i}$ to $S^{*}$ , thus $t\ne r$ . Consider the sub-graph $H'=\left(V\left(G\right),S^{*}\cup\left\{ e_{i}\right\} \right)$ . The edge $e_{i}$ connects now the terminals $t$ and $r$ , and that is the only violation in $H'$ . Since $H'$ is a sub-graph of a tree there is only one path connecting $t$ and $r$ and it must contains the path $r\rightsquigarrow u$ , so removing the edge $e_{j}$ will break the connection between $t,r$ leading to a valid solution $S'=\left(S^{*}\cup\left\{ e_{i}\right\} \right)\backslash\left\{ e_{j}\right\}$ . By the assumption that $w\left(e_{j}\right)\le w\left(e_{i}\right)$ the weight of $S'$ can only increase (in fact, the optimality of $S^{*}$ forces $w\left(e_{j}\right)=w\left(e_{i}\right)$ ) and we get an optimal solution that contains $S_{i}$ , therefore $\mathcal{X}_{i}\ne\emptyset$ , contradiction.