I'm stuck with this particular question. Can someone explain/help me?
Suppose we construct a graph in $WS(n,k,p)$, starting from the n vertices in a ring, where each vertex is connected to its first $\frac k2$ right-hand and left-hand neighbors. What is the probability that none of the edges in this original graph is redirected during the construction of the ultimate graph?
If your graph is undirected, you have $n*k$ vertices connected by $\frac{n*k}{2}$ edges. Probability of each edge to be rewired (redirected) is $p$, and probability that each edge won't be rewired is $1-p$. Then, you have $\frac{n*k}{2}$ independent events each with the probability of $1-p$. So, probability that none of your edges will be redirected is: $$(\frac{n*k}{2})^{1-p}$$
Please note that there is also a possibility that your new graph would form a ring lattice where vertices are shuffled.