 Solution

Choose a uniform random permutation of the $n$ vertices, giving every one of the $n!$ orders the same probability. For a fixed vertex $i$, consider $i$ together with its $d_i$ graph neighbours. The relative order of these $d_i+1$ vertices is uniform, so each is equally likely to be first. The membership rule for $S(\sigma )$ therefore givesLet $I_i$ be the indicator random variable of this event. The cardinality is $|S(\sigma )|={\sum }_{i=1}^n{I}_i$, and linearity of expectation givesThe indicator random variables are generally dependent; only the uniform random permutation and linearity of expectation were needed. An isolated vertex has $d_i=0$ and is always included, as the formula correctly predicts.