If there are more than 1 topological sorting of a DAG is possible, which of the following is true.

Category: QuestionsIf there are more than 1 topological sorting of a DAG is possible, which of the following is true.
Editor">Editor Staff asked 2 months ago

If there are more than 1 topological sorting of a DAG is possible, which of the following is true.
 
(a) Many Hamiltonian paths are possible
 
(b) No Hamiltonian path is possible
 
(c) Exactly 1 Hamiltonian path is possible
 
(d) Given information is insufficient to comment anything
 
The above asked question is from Directed Acyclic Graph topic in portion Graph of Data Structures & Algorithms I
 
This question was addressed to me in my homework.

1 Answers
Editor">Editor Staff answered 2 months ago

Correct answer is (b) No Hamiltonian path is possible
 
The best explanation: For a Hamiltonian path to exist all the vertices must be connected with a path, had that happened there would have been a unique topological sort.