 Solution

Consider any edge $\{u,v\}$ of the simple graph. One endpoint comes first in the permutation $\sigma$; suppose it is $u$. Then $v$ has a graph neighbour preceding it, namely $u$, so $v\notin S(\sigma )$. Therefore no edge has both endpoints in $S(\sigma )$:This argument uses only the order of the endpoints, with no random choice required.