The expected connection cost of the solution S 1 is O(1) times that of S 0 .
combining the two lemmas, we have that the expected cost of the solution S 1 is at most O(1/ )opt, finishing the proof of Theorem 6.