Solution
= 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)$:
$$
\boxed{S(\sigma)\text{ is an independent set for every }\sigma.}
$$
This argument uses only the order of the endpoints, with no random choice required.