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?