# Equation relating extremal properties of graphs to probability of a cycle existing

Does some function exist that takes a desired probability of a certain cycle existing in a random graph as input and outputs the extremal properties of a graph to achieve that probability?

For example, is there a way to answer a question of the form 'what is the smallest number of nodes/edges such that the probability that a random graph contains an Eulerian/Hamiltonian cycle is less than p'?

## 1 Answer

For the usual types of random graphs, the probability of existence of a Hamiltonian cycle will be essentially impossible to compute, however the expected number of Hamiltonian cycles is very easy: you just take the probability of a particular possibility being a cycle and multiply by the number of possible cycles. If the expected number of Hamiltonian cycles is less than $1$, that gives you an upper bound on the probability of there being a Hamiltonian cycle.