0
$\begingroup$

If we have a connected undirected graph $G = (V,E)$, we want to find an algorithm($O(|V|+|E|)$ that finds if there is such an edge $e\in E$ that $G$ will remain connected after its deletion.

Also is there a way to speed up to $O(|V|)$?

  • 0
    Could this help: [Design an algorithm to check if a given graph is connected](http://wiki.answers.com/Q/Design_an_algorithm_to_check_if_a_given_graph_is_connected)?2012-04-05

1 Answers 1

2

If $G$ is connected, then it contains a spanning tree containing $|V|-1$ edges. Any edge not in the spanning tree can be deleted without losing connectedness. Thus if $|E|\ge|V|$ then the answer is "yes".

On the other hand if $|E|<|V|$, then the graph after deleting any edge will have too few edges to contain a spanning tree, and therefore cannot be connected. So if $|E|<|V|$ the answer is "no".

Thus the only thing you need to do is count the vertices and edges. With a sufficiently redundant (but still reasonable) representation of the graph this can even be a $O(1)$ operation.


If you want to find a deleteable edge, do a depth-first search and look for back edges. A back edge is easily seen to be deleteable.