Gate CS-2013 Question Paper With Solutions

Q. 18 Which of the following statements are TRUE?

1. The problem of determining whether there exists
   a cycle in an undirected graph is in P.
2. The problem of determining whether there exists
   a cycle in an undirected graph is in NP.
3. If a problem A is NP-Complete, there exists a 
   non-deterministic polynomial time algorithm to solve A.

(A) 1, 2 and 3

(B) 1 and 2 only

(C) 2 and 3 only

(D) 1 and 3 only

Answer: (A)

Explanation: