Question

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. 3 only
• B. 1 and 3 only
• C. 1, 2 and 3
• D. 2 only

Answer 1

The correct option is C 1, 2 and 3

1. By depth first search we can find whether there exits a cycle in an undirected graph in $O\left(n^2\right)$ times so it is P problem.

2. As $P\subseteq NP$ so this problem will also be considered as NP problem.

3. This is the definition of NP-complete so it is trivially true.

So option (a) is correct