Consider a non-oriented graph with n vertices: {1 ... n}.
Let $ p \in [0,1]$ is the probability of having an edge between any two vertices. The probability of having an edge is the same for any two vertices.
So I have two tasks:
- a) Find the probability of having a hamiltonian cycle in the graph.
- b) What is the probability of havin a hamiltonian cycle if we know that $(1)-(2) \dots - (k)$ is a path in the graph.
My attempt for a):
So we have (n - 1)! different options for a hamiltonian cycle.
The probability of having (for example) this ham cycle: $(1)-(2) \dots (n) - (1)$ is $p^{n}$
So the probability that the graph DOES NOT contain a ham cycle is $1 - (p^n)^{(n-1)!} $
But the problem is that I consider that the existence of the different ham paths are indpendent, which is obviously not true.
Any tips?