Question taken from "The Algorithm Design Manual" by Steven S. Skiena, 1997.
A vertex cover of a graph $G=(V,E)$ is a subset of vertices $V'\subseteq V$ such that every edge $e\in E$ contains at least one vertex from $V′$.
Delete all the leaves from any depth-first search tree of $G$. Must the remaining vertices form a vertex cover of $G$? Give a proof or a counterexample.
Answer given :
If the tree has more than one vertex, then yes. The remaining vertices are still the vertex cover because for every edge e∈E incident on the leaves, their other end-point is still in the remaining tree.
The answer is right for undirected graphs. But I think there exist counterexamples to this question using directed graphs.
If we are using DFS starting from vertex $a$ and we are traversing in alphabetical order, i.e. explore b first, then we end up with two tree edges, which are $(a,b)$ and $(a,c)$. Therefore, $b$ and $c$ are leaf-vertices.
But here if are going to delete vertices $b$ and $c$ the edge $(c,b)$ has no incident vertices which are contained in our vertex cover.
Am I right? I am confused actually.