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
1) We can use "Depth First Search" Algorithm, to check it there is a cycle is an undirected graph. It we encounter any ''back edge" in "Depth first search" then given undirected graph has a cycle. Also, if there is a cycle in the undirected graph, we must encounter a "back edge" is DFS. And, DFS can be done in O (|E| + |V|) time for graph G = (V, E). So, it can is in F. 2) P < NP, so, it is also in NP. 3) NP-complete problem ANP. By, Definition Every problem in NP can be solved in polynomial time using non-deterministic turing machine. So, Answer is (A) i.e. 1, 2, and 3 are true.
