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