# A longest path can be found using DFS

The following is a Yes/No question. In an undirected unweighted graph $G$, a longest path between two given vertices $s$ and $t$ can be found using Depth-first search?

If it is possible to use DFS to find such a path, show the algorithm.

My thoughts: My answer is Yes. I would solve it by brute force using backtracking, my DFS. And the class of the graph doesn't really matter here. Am I right?

• Why do you think that DFS can find a longest path? What do you mean by "how could it be the algorithm"? I'm having a hard time understanding what you are asking. I encourage you to edit the question to provide more context/motivation, explain what your question is, and tell us what your thoughts are. – D.W. Sep 23 '18 at 23:59
• Is it better now? I – jonaprieto Sep 24 '18 at 7:30
• Hint: what would this imply for P vs NP? – Peter Taylor Sep 24 '18 at 13:44
• What do you mean by 'longest path'? If you mean the common definition, then as @Peter indicated, the wikipedia item tells us the problem to find the longest path between two vertices is NP-complete. – Apass.Jack Sep 25 '18 at 5:40