Prize collecting steiner tree

Question

I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of Approximation Algorithms by Williamson and Shmoys). I don't understand the second line in the proof for Lemma 5.16: .

It seems to me that $V-V(T)$ is a much larger set than $U$. So, how can the total penalty for this set be upper bounded by the total penalty of a set that is much smaller?

Answer 1

$T$ is a tree that connects the chosen subset of terminals $U$. Thus $U$ is a subset of $V(T)$, and $V \setminus V(T)$ is a subset of $V \setminus U$ (we're summing $i$ not in $U$).