La respuesta depende mucho de cómo se defina "gráfico cúbico aleatorio" con $n$ vértices (necesariamente $n$ es par), podemos intentar lo siguiente para encontrar los circuitos de Hamilton:
Fijar un vértice $a_1$ Elige uno de sus vecinos $a_2$ al azar. Entonces, asumiendo que tenemos $a_1a_2\ldots a_k$ con $k\ge 2$ , lanza una moneda para decidir cuál de los otros dos (es decir $\ne a_{k-1}$ ) vecinos de $a_k$ para elegir como $a_{k+1}$ y continuar. Puede ser adecuado asumir que $a_ka_{k+1}$ puede ser cualquiera de los $3(n-k)$ aristas a un "nuevo" vértice, o cualquiera de los $k-3$ aristas aún no utilizadas a uno de los vértices $a_2,\ldots, a_{k-2}$ o cualquiera de los dos bordes no utilizados para $a_1$ . Esto nos hace suponer que la probabilidad de alcanzar un nuevo vértice es $\frac{3(n-k)}{3(n-k)+(k-3)+2}=1-\frac{k-1}{3n-2k-1} $ . Y cuando $k=n$ la probabilidad de volver con éxito a $a_1$ es $\frac{2}{n-1} $ . Esto sugiere que hay alrededor de $$\tag13\cdot 2^n\cdot\prod_{k=2}^{n-1}\frac{3(n-k)}{3n-2k-1}\cdot \frac2{n-1}=3^{n-1}2^{n+1}(n-2)!\frac{(3n/2-3)!\cdot 2^{3n/2-3}}{(3n-5)!\cdot (n/2)!\cdot2^{n/2}}\cdot\frac1{n-1} $$ Ciclos de Hamilton.
O: Hay $\frac12(n-1)!$ Ciclos de Hamilton en el gráfico completo $K_n$ . Para cada una de ellas, la probabilidad de que la primera arista esté también en $G$ es $\frac3{n-1}$ para las aristas posteriores, la probabilidad de que la arista esté en $G$ , dado que el borde anterior está en $G$ es $\frac{2}{n-2}$ ; deberíamos hacer una consideración especial para la arista final, pero ignórala. Con este ciclo Hamilton de $K_n$ también está en $G$ con probabilidad $ \frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}$ , lo que da un número total esperado de $$ \frac12(n-1)!\cdot \frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}=\frac{3\cdot 2^{n-2}\cdot (n-2)!}{(n-2)^{n-1}}$$ Ciclos de Hamilton. Con Stirling, esto se simplifica a $$\tag2\approx {3\cdot \left(\frac 2e\right)^{n-2}\sqrt{\frac{2\pi}{n-2}}}\approx 0.$$
O bien: Si eliminamos una arista al azar de un grafo cúbico, obtenemos dos vértices de grado $2$ que se puede sustituir por una arista que conecte directamente a sus vecinos, con lo que se obtiene un gráfico cúbico con dos vértices menos. Sin embargo, este paso puede haber producido una arista doble, en cuyo caso podemos eliminar una de las aristas, obteniendo de nuevo vértices de grado dos, que pueden ser eliminados. Esto podría repetirse, pero para grandes $n$ podemos considerar que cada uno de estos casos especiales es raro. Así, los circuitos Hamilton de $G$ que no utilizan una arista concreta se corresponden con los circuitos Hamilton de un grafo cúbico más pequeño. Para un vértice fijo $a_0$ cada circuito Hailton evita precisamente una de las tres aristas incidentes. Por lo tanto, esto sugiere que el número esperado de circuitos para un $n$ -cúbico de vértices son esencialmente $3$ veces el número esperado del número de circuitos en un $(n-2)$ -de vértices del gráfico cúbico, por lo que su recuento debe ser $$\tag3 \sim 3^{n/2}.$$
Ahora que he obtenido heurísticamente (!) tres resultados totalmente diferentes, parece que esta respuesta debería considerarse más bien como un comentario sobredimensionado - suspiro.
