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 ...


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