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?
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, which points to Randomly Traceable Graphs, Chartrand and Kronk, SIAM J. Appl. Math., 16(4), 696–700, doi:10.1137/0116056 as characterising these graphs as precisely the graphs you mention in the question.
