5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Why do you divice by 2? Otherwise, yes; trees are connected and have exactly $n-1$ edges. $\endgroup$ – G. Bach Jan 22 '16 at 21:47
  • $\begingroup$ @G. Bach I divide by two because I have an adjacencies list representation of an undirected graph. $\endgroup$ – user45244 Jan 23 '16 at 0:00
  • $\begingroup$ "Minimally connected" is what graph theorists just call a tree, i.e., connected with no cycles. And those have $n - 1$ edges for $n$ vertices. $\endgroup$ – vonbrand Jan 23 '16 at 0:36
  • 2
    $\begingroup$ Oh, and your proposal will output False for the empty graph, so if you consider that connected then you'll need to handle it as a special case. ​ ​ $\endgroup$ – user12859 Jan 23 '16 at 3:34
4
$\begingroup$

If $G$ is an undirected graph, it's a standard lemma that the following are equivalent:

  • $G$ is a tree.

  • $G$ is connected and has no cycles.

  • $G$ is connected and the number of edges is one less than the number of vertices.

Therefore, yes, your solution is also correct.

(The authors' solution does have the benefit of giving you a relatively simple setting where you can think through the properties of depth-first search in a deep way. There are other problems that aren't solved so easily, and where the best solution involves some other sort of modification to depth-first search.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.