Probabilistic Proof for Turan's Theorem I was referring this proof for Turan's Theorem. But I am not very sure about the correctness (or my understanding) of the proof, specifically the part where they claim the probability of selecting a vertex as $$p(u) \ge \frac{1}{d(u)+1}$$
The issue is that with this inequality, the probabilities may add up to greater than 1. For example consider the following graph 

Here we will get $$\sum_{u}p(u) = p(1) + p(2) + p(3) \ge \frac{1}{2} + \frac{1}{2} + \frac{1}{3} > 1$$
So is this proof incorrect?
 A: That proof is a bit informal. What you add, are not probabilities, but expected values, which happen to be equal to the probabilities, and the author of the proof didn't want to dwell too much on this. If you want to make it more formal, define:
$$X_u = \begin{cases}1 & \text{ if }u \in S, \\0 & \text{ otherwise}.\end{cases}$$
Observe that $\mathbb{E}X_u = \mathbb{P}(u \in S) \geq \frac{1}{\deg(u)+1}$ and thus, by linearity of expectation
$$\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}.$$
I hope this helps $\ddot\smile$
Edit: Regarding the comment, with the standard greedy algorithm the equality would be incorrect. Sometimes you can include $u$ in $S$ even if some of its neighbors were checked earlier in the permutation, but were not picked because of their neighbors. For example, take a path consisting of four vertices $v_0 \leftrightarrow v_1 \leftrightarrow v_2 \leftrightarrow v_3$ and calculate $P(v_2 \in S)$ given the permutation:
\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}
which gives $\frac{9}{24} > \frac{8}{24} = \frac{1}{\deg(v_2)+1}$.
