Which of the following are correct about Hamiltonian problems? A. The Hamiltonian cycle problem is NP-complete. B. If G is an undirected bipartite graph with an odd number of vertices, then G is Hamiltonian. C. The Hamiltonian path problem cannot be solved in polynomial time on a directed acyclic graph. D. If G is a connected undirected graph with at least three vertices, then G³ (obtained by connecting all pairs of vertices joined by a path of length at most 3 in G) is Hamiltonian. E. If any NP-complete problem is polynomial-time solvable, then P = NP.

1. AA, B, C only
2. BB, D, E only
3. CA, D, E only
4. DA, C, E only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. A, D, E only

Explanation

A, D and E are true (D is a known result about the cube of a connected graph). A bipartite graph with an odd number of vertices can never be Hamiltonian, since a cycle alternates sides (B false). On a DAG, a Hamiltonian path is found in linear time with a topological sort (C false).