Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|)$?

share|cite|improve this question
What is a "coherent" graph? Google doesn't seem to find anything relevant? Do you mean "connected"? – Henning Makholm Dec 31 '11 at 15:12
Yes it is connected. I hate these names cause I always forget them. – johnfillips21 Dec 31 '11 at 15:16
Could this help: Design an algorithm to check if a given graph is connected? – draks ... Apr 5 '12 at 10:44

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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