This was a question asked on a previous exam:
Bob is looking for a Hamiltonian cycle in a graph with $n$ vertices. His plan is to start with an arbitrary vertex, write down an adjacent vertex, and continue until either he has written $n$ distinct vertices and can return to the start vertex, or is forced to repeat a vertex. He will never write the same string of vertices, and can choose a new starting vertex each time he tries. Approximately how many strings will Bob need to write to prove there is no Hamiltonian cycle?
I know of Dirac's Theorem, but otherwise have no clue how to go about this problem.