6
$\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.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Why do you divice by 2? Otherwise, yes; trees are connected and have exactly $n-1$ edges. $\endgroup$
    – G. Bach
    Jan 22, 2016 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, 2016 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, 2016 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, 2016 at 3:34

1 Answer 1

Reset to default
5
$\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.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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