Complexity class of Determining Hamiltonian cycle

Question

I Know that determining Hamiltonian cycle in a graph is NP complete. For the sake of my clarification, I just want to know that whether the problem remains NP complete with following restrictions ?

1) Graph is undirected , and every node has degree two.

Any help will be appreciated. Thanks.

Answer 1

If every node has degree two, then the test for a Hamiltonian cycle boils down to testing connectivity, since the graph must then consist of 0 or more disconnected cycles.

The algorithm is as follows:

Choose a starting node v
marked[v] = true
x := v
while x has an unmarked neighbour u
    x := u
    marked[u] = true
if all nodes in the graph are marked, return true, else return false

Suppose we see $v_1 \cdots v_n$ in this process. Since each node has degree 2, we only stop when we see a node with both its neighbors marked, so $v_1 \cdots v_n$ is a cycle in the graph. Since we see two edges from each $v_i$, there can be no other nodes connected to any $v_i$ that are unmarked. Thus, either $v_1 \cdots v_n$ is all nodes in the graph, and there is a cycle, or there is another connected component, and there is not a cycle.

Clearly this test is linear time, so the problem is in $P$.