Esa prueba es un poco informal. Lo que se añade, no son probabilidades, sino valores esperados, que resultan ser iguales a las probabilidades, y el autor de la prueba no quiso detenerse demasiado en esto. Si quieres hacerlo más formal, define:
$$X_u = \begin{cases}1 & \text{ if }u \in S, \\0 & \text{ otherwise}.\end{cases}$$
Observe que $\mathbb{E}X_u = \mathbb{P}(u \in S) \geq \frac{1}{\deg(u)+1}$ y por tanto, por linealidad de la expectativa
$$\mathbb{E}|S| = \mathbb{E}\left(\sum_u X_u\right)=\sum_u\mathbb{E}X_u\geq\sum_u\frac{1}{\deg(u)+1}.$$
Espero que esto ayude $\ddot\smile$
Editar: Respecto al comentario, con el algoritmo codicioso estándar la igualdad sería incorrecta. A veces se puede incluir $u$ en $S$ incluso si algunos de sus vecinos fueron comprobados antes en la permutación, pero no fueron elegidos debido a sus vecinos. Por ejemplo, tomemos un camino formado por cuatro vértices $v_0 \leftrightarrow v_1 \leftrightarrow v_2 \leftrightarrow v_3$ y calcular $P(v_2 \in S)$ dada la permutación:
\begin{align} \langle v_2, *, *, *\rangle &\to 6 \times 1 \\ \langle v_0, v_2, *, *\rangle &\to 2 \times 1 \\ \langle *, v_2, *, *\rangle &\to 4 \times 0 \\ \langle v_0, v_1, v_2, v_3\rangle &\to 1 \times 1 \\ \langle v_0, v_3, v_2, v_1\rangle &\to 1 \times 0 \\ \langle *, *, v_2, *\rangle &\to 4 \times 0 \\ \langle *, *, *, v_2\rangle &\to 6 \times 0 \end{align}
que da $\frac{9}{24} > \frac{8}{24} = \frac{1}{\deg(v_2)+1}$ .
