<p>This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for <em>greedy Hamiltonian path</em> turned up: <em>Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests</em>, Tankusa and Tarsib, <a href="http://dx.doi.org/10.1016/j.disc.2006.09.031">doi:10.1016/j.disc.2006.09.031</a>, which points to <em>Randomly Traceable Graphs</em>, Chartrand and Kronk, SIAM J. Appl. Math., 16(4), 696–700, <a href="http://dx.doi.org/10.1137/0116056">doi:10.1137/0116056</a> as characterising these graphs as precisely the graphs you mention in the question.</p>

CC BY-SA 3.0
2016-06-06T11:00:48.583Z
2016-06-06T11:00:48.583Z
Peter Taylor
<p>For which undirected graphs are all depth-first-search trees (for all possible starting vertices and for all choices of which neighbors to search first) directed paths? That is, every DFS tree should have only one leaf, and every other vertex should have exactly one child.</p>

<p>For instance, it's true for cycles, complete graphs, and balanced complete bipartite graphs.</p>

<p>Finding a DFS tree that is not a path is obviously in NP. Is it NP-complete, or polynomial?</p>

<graph-theory>
For which graphs is the DFS tree always a path?
David Eppstein
# For which graphs is the DFS tree always a path?

(Asked by: username_0 on 2016-06-06)

For which undirected graphs are all depth-first-search trees (for all possible starting vertices and for all choices of which neighbors to search first) directed paths? That is, every DFS tree should have only one leaf, and every other vertex should have exactly one child.

For instance, it's true for cycles, complete graphs, and balanced complete bipartite graphs.

Finding a DFS tree that is not a path is obviously in NP. Is it NP-complete, or polynomial?

**Tags:** graph-theory

---

## 1 answers

### Answer by username_1 on 2016-06-06. Score: 13 | Accepted answer

This is equivalent to the property that you can construct a Hamiltonian path by greedily taking an arbitrary edge at every vertex. Searching for *greedy Hamiltonian path* turned up: *Greedily constructing Hamiltonian paths, Hamiltonian cycles and maximum linear forests*, Tankusa and Tarsib, [doi:10.1016/j.disc.2006.09.031](http://dx.doi.org/10.1016/j.disc.2006.09.031), which points to *Randomly Traceable Graphs*, Chartrand and Kronk, SIAM J. Appl. Math., 16(4), 696–700, [doi:10.1137/0116056](http://dx.doi.org/10.1137/0116056) as characterising these graphs as precisely the graphs you mention in the question.


---

