# How many strings will Bob need to write to prove there is no Hamiltonian cycle in a graph with n vertices?

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?

• Depends on the graph. In extreme cases, one string suffices. – Peter Taylor Dec 9 '19 at 11:04
• Did Bob Dylan write the title to this question? :) – user856 Dec 9 '19 at 11:47
• @Rahul, it doesn't scan very well. – Gerry Myerson Dec 9 '19 at 11:54

Determining whether a graph $$G=(V,E)$$ (undirected or directed) contains an Hamilton cycle (or even path) is NP-complete problem. Roughly speaking, it means that in order to solve this problem you'll have to go though every possibility.
Regarding your question, the method you are using is called pruning. Asymptotically speaking, it's worst case (or even average case) run time is $${O}(2^{n})$$. Therefore, the answer to your question is $${O}(2^{n})$$ strings in the worst case.