# Probability of finding a Hamilton circuit in a graph

In short, I would like to know either/both the probability that there exists a Hamiltonian circuit within a graph, or the number of circuits expected to exist. (Without actually finding all the circuits). If I run an algorithm to find all circuits, how many should I expect to find, if any? I am fine with a close approximation if it simplifies the calculations substantially.

If I have a given number of vertices and the average number of edges, is this enough information? Each vertex may have many out-edges but no two vertices share more than one edge. Also, a vertex cannot belong to two circuits. Once a circuit is found, those vertices that comprise it are removed from the graph.

My example graph has 10,000 vertices and each vertex has three out-edges to other vertices.

And a follow up question: How could I formulate the question to figure out the minimum average number of out-edges per vertex to give me an arbitrary level of certainty that I would find at least one circuit? Stated another way, if I want 50% certainty in finding a circuit, and I have 10,000 vertices, what is the minimum number of out-edges each vertex should have? (not the average, but actual minimum)

I have some scratchpad notes where I've worked this out, but would really appreciate the guidance of someone more knowledgeable. Thanks!

The answer depends a lot on how one defines "random cubic graph" with $n$ vertices (necessarily $n$ is even), we may try the following to find Hamilton circuits:
Fix a vertex $a_1$, pick one of its neighbours $a_2$ at random. Then, assuming we have $a_1a_2\ldots a_k$ with $k\ge 2$, toss a coin to decide which of the other two (i.e. $\ne a_{k-1}$) neighbours of $a_k$ to pick as $a_{k+1}$ and continue. It may be adequate to assume that $a_ka_{k+1}$ could be any of the $3(n-k)$ edges to a "new" vertex, or any of the $k-3$ not yet used edges to one of the vertices $a_2,\ldots, a_{k-2}$, or any of the two not yest used edges to $a_1$. This makes us guess that the probability to hit a new vertex is $\frac{3(n-k)}{3(n-k)+(k-3)+2}=1-\frac{k-1}{3n-2k-1}$. And when $k=n$, the probability of succesfully coming back to $a_1$ is $\frac{2}{n-1}$. This would suggest that there are about $$\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}$$ Hamilton cycles.
Or: There are $\frac12(n-1)!$ Hamilton cycles in the complete graph $K_n$. For each of these, the probability that the first edge is also in $G$, is $\frac3{n-1}$; for later edges, the probybility that the edge is in $G$, given that the previous edge is in $G$, is $\frac{2}{n-2}$; we should make a special consideration for the final edge, but ignore that. With this Hamilton cycle of $K_n$ is also in $G$ with probability $\frac3{n-1}\cdot\left(\frac2{n-2}\right)^{n-1}$, giving a total expected number of $$\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}}$$ Hamilton cycles. With Stirling, this simplifies to $$\tag2\approx {3\cdot \left(\frac 2e\right)^{n-2}\sqrt{\frac{2\pi}{n-2}}}\approx 0.$$
Or: If we remove a random edge from a cubic graph, we produce two vertices of degree $2$, which can be replaced with an edge directly connectng their neighbours, thus resulting in a cubic graph with two vertices less. However, this step may have produced a double edge, in which case we can drop one of the edges, obtain degree-two vertices again, which can be removed. This could repeat, but for large $n$ we can consider each of these special cases rare. Thus the Hamilton circuits of $G$ that do not use a specific edge are in correspondance with the Hamilton circuits of a smaller cubic graph. For a fixed vertex $a_0$, each Hailton circuit avoids precisely one of the three incident edges. Hence this suggests that the expected number of circuits for an $n$-vertex cubic graph are essentially $3$ times the expected number of the number of circuits in an $(n-2)$-vertex cubic graph, so their count should be $$\tag3 \sim 3^{n/2}.$$