#dfs

Question

An undirected graph said to be hamiltonian if it has cycle containing all the vertices. Any DFS tree on a hamiltonian graph must have depth V-1 ?  true of  false

Answer 1

It should be false..

Since dfs  can find the cycle in O(n+e) time.

But it will not find Hamiltonian cycle.

In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that is a cycle. Determining whether such paths and cycles exist in graphs is the Hamiltonian path problem, which is NP-complete.

Because of it not able to find Hamiltonian cycle depth should be less than v-1.

https://en.m.wikipedia.org/wiki/Hamiltonian_path

Comments

@air1. MITian's are right :) :) . Got one graph. Consider the following graph:

Now, ABCDE is hamiltonian path. But if I add the edges in the order A-C, C-B, C-D, D-E then length is less than $(V-1)$.

So, finally answer is false.

---

One Hamiltonian cycle in the above graph is 12453. The cycle found is dependent on the order in which neighbouring nodes are visited. If the nodes are visited in the order 13452, the depth of the DFS tree is just 3.

EDIT: Sorry didn't notice you had already posted that comment.

---

@air1. No issues bro.Thats was really good question :)