GATE CS 2013 Q18 — Undecidability

Let us analyze each statement individually:

1. Statement 1: "The problem of determining whether there exists a cycle in an undirected graph is in $P$."
   We can detect a cycle in an undirected graph using Depth First Search (DFS), Breadth First Search (BFS), or a Disjoint Set Union (DSU) data structure. The time complexity of these algorithms is $O(V + E)$, which is polynomial in the size of the input. Thus, the problem belongs to class $P$. (True)


2. Statement 2: "The problem of determining whether there exists a cycle in an undirected graph is in $NP$."
   Since the class $P$ is a subset of $NP$ ($P \subseteq NP$), any problem that can be solved in polynomial time on a deterministic Turing machine can also be solved in polynomial time on a non-deterministic Turing machine. Since the problem is in $P$, it is also in $NP$. (True)


3. Statement 3: "If a problem $A$ is $NP\text{-Complete}$, there exists a non-deterministic polynomial time algorithm to solve $A$."
   By definition, a language/problem $A$ is $NP\text{-Complete}$ if and only if:
   1. $A \in NP$, and
   2. Every problem $B \in NP$ is polynomial-time reducible to $A$ ($A$ is $NP\text{-Hard}$).
   Since $A \in NP$, there must exist a non-deterministic polynomial-time algorithm that decides $A$. (True)

Since statements 1, 2, and 3 are all true, the correct option is A.