Probability of choosing a graph with Hamiltonian cycle

Question

Given $N$ labeled points in a plane one can construct $2^{N(N-1)/2}$ graphs(Unweighted, undirected) with them. Is there any theorem that gives the probability of choosing at random from these a graph having a Hamiltonian cycle? Does a similar result exist for Eulerian cycles?

Answer 1

Yes, a lot of work has been done on these kinds of questions. Choosing a graph on $n$ vertices at random is the same as including each edge in the graph with probability $\frac{1}{2}$, independently of the other edges. You get a more general model of random graphs if you choose each edge with probability $p$. This model is known as $G_{n,p}$.

It turns out that for any constant $p>0$, the probability that $G$ contains a Hamiltonian cycle tends to 1 when $n$ tends to infinity. In fact, this is true whenever $p>\frac{c \log(n)}{n}$ for some constant $c$. In particular this is true for $p=\frac12$, which is the setting that you describe.

Regarding Eulerian cycles, since a Eulerian cycle exists iff the degrees are all even and the probability that a vertex has even degree is about $\frac12$, the probability that there is a Eulerian cycle is about $2^{-n}$.

For further reading, I recommend the book Random Graphs by Bollobas.