# Deletion on a connected undirected graph

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

-
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.