Seleccione un vértice de partida y siga los bordes, eligiendo el extremo de cada punto al azar a medida que avanza. Tarde o temprano va a terminar en un vértice que han sido antes. Si ese vértice es el punto de partida de vértice, entonces su borde inicial fue parte de un ciclo, de lo contrario no lo era.
Mediante este procedimiento, vamos a derivar la probabilidad de que el borde inicial fue parte de un ciclo que contiene a $N-a$ vértices para $0\le a< N$ (estoy parametrización por el número de vértices no en el ciclo, que pasa a hacer las siguientes fórmulas salen mejor). Para que esto suceda, primero tenemos que seleccionar una sin embargo, no utilizados vértice $N-a-1$ veces, lo que ocurre con probabilidad
$$ \frac{N-1}{N} \frac{N-2}{N}\cdots \frac{a+1}{N} = \frac{(N-1)!}{a! N^{N-a-1}}$$
- y luego tenemos que seleccionar el vértice inicial, para un factor adicional de $\frac 1N$.
Sumando sobre todas las duraciones del ciclo, la probabilidad de que el borde inicial para ser parte de cualquier ciclo de
$$P_N = \sum_{a=0}^{N-1} \frac{(N-1)!}{a!N^{N-a}} = \frac{(N-1)!}{N^N} \sum_{a=0}^{N-1} \frac{N^a}{a!}$$
Reconociendo la suma en la expresión final como una suma parcial de la serie para $e^N$, y usando la aproximación de Stirling para el factorial, podemos enlazado a esta probabilidad de arriba como
$$P_N < \frac{(N-1)!}{N^N} e^N = N!\frac{e^N}{N^{N+1}} \approx \sqrt{2\pi N}\frac{N^N}{e^N}\frac{e^N}{N^{N+1}} = \sqrt{\frac{2\pi}{N}} $$
pero este es un factor de al menos $2$ demasiado alto, debido a la exponencial de la serie fue cortado a la derecha en su mayor plazo (y los términos de la serie completa caer más lento después de la cúspide de ellos aumenta, para empezar).
Edit: estoy informado de que $\sum_{n=0}^{k} \frac{k^n}{n!} \sim \frac{e^k}{2}$, lo que nos permite refinar la estimación para una real aproximación:
$$ P_N \approx \sqrt{\frac{\pi}{2N}} - \frac{1}{N}$$
