3

The classical version of this question is for Hamiltonian cycles, but there is probably little difference. I will only consider the version with cycles. In order for a graph to contain a Hamiltonian cycle, the minimal degree should be at least 2. This is essentially the only obstruction for Hamiltonicity. To state this we need to define the following ...


3

No. A graph with only the edges of a polygon has an Hamilton circle, but the degree of each vertex is 2.


3

The statement in CRLS is not wrong in any case; an algorithm that runs in $O(n)$ time also runs in $O(n^2)$ time. Of course, it would be more precise to state the running time as $O(n)$ if this were true, so why doesn't CLRS do this? First off, this depends on the encoding chosen for $G$. If an adjacency matrix is used, a graph with $V$ vertices always has ...


1

Perhaps the most comprehensive list is available via ISGCI, along with references. Examples for which the problem is easy include bounded treewidth graphs and many subclasses of chordal graphs. As to why exponential time seems unavoidable in general, we don't strictly know. As far as we know, P = NP is also possible.


Only top voted, non community-wiki answers of a minimum length are eligible