1 votes 1 votes TRUE / FALSE Explain Please.. An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Any DFS tree on a Hamiltonian graph must have depth V − 1. Algorithms graph-algorithms shortest-path + – Rishav Kumar Singh asked Jul 30, 2018 Rishav Kumar Singh 780 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Shaik Masthan commented Jul 31, 2018 reply Follow Share Cycle means A-B-C-D-E - A but you stop at E only ===> Your DFA tree A-B-C-D-E 0 votes 0 votes Nitesh Choudhary commented Jul 31, 2018 reply Follow Share it is not always true . so statement is False 0 votes 0 votes Shaik Masthan commented Jul 31, 2018 reply Follow Share Could you G the counter example... I am not getting 0 votes 0 votes Shaik Masthan commented Aug 6, 2018 reply Follow Share Actually, if the question is right then it must be depend upon the graph if the question is An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices. Atleast one DFS tree on a Hamiltonian graph must have depth V − 1. Then it is true 1 votes 1 votes Prince Sindhiya commented Aug 6, 2018 reply Follow Share https://gateoverflow.in/62170/%23dfs 0 votes 0 votes Shaik Masthan commented Aug 6, 2018 reply Follow Share @Prince Sindhiya, the answer given in the link is ir-relevant to the question. consider following Hamilton graphs 1 votes 1 votes Rishav Kumar Singh commented Aug 9, 2018 reply Follow Share Shaik Masthan great explanation 0 votes 0 votes Please log in or register to add a comment.