# Vertex cover of a graph by removing leaf-vertices from a DFS tree

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.

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.

My question:

The answer is right for undirected graphs. But I think there exist counterexamples to this question using directed graphs.

For example: 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.

• I believe the question and the book are strictly talking about undirected graphs. – Juho Jul 11 '16 at 17:32
• @Juho As it was not specified explicitly so I thought of directed case – ViX28 Jul 11 '16 at 17:39
• If you want to consider directed graphs, you will have to define what a vertex cover is (on a directed graph). – Juho Jul 11 '16 at 17:51

To consider directed graphs, we first need to define what a vertex cover is on a directed graph. Well, we can say it is a subset of vertices such that every arc is incident to at least one vertex in the subset. Again, the book makes no claim about such directed vertex covers. If you are now asking "does $\{ a \}$ form a (directed) vertex cover as per our definition?", the answer is NO as you correctly observed.