I'm trying to solve a practice problem in Elements of Programming Interviews (19.4) and I am a bit confused. The question is to determine if an undirected connected graph is minimally connected.
The authors define minimally connected as "it is connected and there is no edge that can be removed while still leaving the graph connected."
This question is equivalent to asking if there are any cycles in the graph.
They authors' solution runs the white-gray-black variant of recursive DFS, and return false if a grey node is visited twice.
It seems to me though, that since you know the graph is connected you can just count the number of edges. Any minimally connected graph, like a binary tree, will have (V - 1) edges.
return num_edges/2 == num_vertices - 1;
So, long story short, is this solution correct for the case of an undirected, connected graph? I checked the books errata and it doesn't mention it.