Random cuts of a cycle ($\mathrm{Pr}(i\leftrightarrow j)=\frac{\left(\genfrac{}{}{0ex}{}{k}{r}\right)+\left(\genfrac{}{}{0ex}{}{n-k}{r}\right)}{\left(\genfrac{}{}{0ex}{}{n}{r}\right)}$)

Choose $r$ distinct edges uniformly from an $n$-vertex cycle graph, with $1\le r\le n$, and delete them. Two specified vertices at oriented distance $k$ remain connected exactly when one of their two complementary edge-disjoint paths is uncut. All cuts must then lie in the other path, giving the displayed probability. The two events are disjoint because at least one edge is cut. Set $\left(\genfrac{}{}{0ex}{}{a}{r}\right)=0$ when $a<r$.

Summing the connectivity indicators for all other vertices gives an expected numberof other vertices in a tagged connected component. The sum identity follows by classifying $(r+1)$-element subsets according to their greatest element. For three cuts this is $(n-3)/2$ other vertices.