TIFR CSE 2020 | Part B | Question: 13

Question

Let $G$ be an undirected graph. An Eulerian cycle of $G$ is a cycle that traverses each edge of $G$ exactly once. A  Hamiltonian cycle of $G$ is a cycle that traverses each vertex of $G$ exactly once. Which of the following must be true?

• A. Checking if $G$ has a Eulerian cycle can be done in polynomial time
• B. Deciding if $G$ has a Hamiltonian cycle is not NP-complete
• C. If $G$ has an Eulerian cycle, then it has a Hamiltonian cycle
• D. A complete graph always has both an Eulerian cycle and a Hamiltonian cycle
• E. All of the other statements are true

Answer 1

$(a)$ True. To check whether a given graph has Eulerian cycle or not, can be done in linear time in terms of input of the graph. So, we can check it in polynomial time. We can store the given undirected graph $G$ in adjacency list and first using DFS, check whether the graph is connected or not. If the graph is connected then check  whether each vertices has even degree or not in the adjacency list representation of the graph and if the graph is not connected then do the same thing for each component of the graph. It takes $\mathcal{O}(|V|+|E|) $ time.

$(b)$ False. To check whether the graph $G$ has Hamiltonian cycle or not, is an NPC problem.

$(c)$ False.

Counter-Example :

Eulerian Cycle : ABDACDEFHGEA

But it does not have any Hamiltonian cycle.

$(d)$ False.

Complete graph $K_4$ does not have a Eulerian cycle because each vertex has degree $3$ which is not even.

But every complete graph always have a Hamiltonian cycle because there exist a path from one vertex to every other vertices.