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?

  • $\begingroup$ This seems reasonable for Eulerian cycles, since it comes down to parity of vertex degrees. Without a characterization of when graphs support a Hamilton cycle, such a result would surprise me, although there might be bounds corresponding to necessary or sufficient conditions for Hamiltonian cycles. $\endgroup$ – Brian Hopkins Jan 21 '15 at 15:14
  • $\begingroup$ I'm am hoping that at least there are some bounds on the probabilities, even if exact results are not known $\endgroup$ – biryani Jan 21 '15 at 15:16
  • $\begingroup$ To compute some initial values of the probability, oeis.org/A003216 gives counts of Hamiltonian graphs by number of vertices up to 11. However, that counts nonisomorphic graphs, which would each appear several times in the construction behind the 2^(n(n-1)/2) count, so there would be more work than just dividing the OEIS numbers by the powers of 2. $\endgroup$ – Brian Hopkins Jan 21 '15 at 15:37

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.