Is there an edge we can delete without disconnecting the graph?

Question

Before I start, yes this is a homework. I would not have posted here if I haven't been trying as hard as I could to solve this one for the last 14 hours and got nowhere.

The problem is as follows: I want to check whether I can delete an edge from a connected undirected graph without disconnecting it or not in O(V) time, not just linear.

What I have reached so far:

A cycle edge can be removed without disconnecting the graph, so I simply check if the graph has a cycle. I have two methods that could be used, one is DFS and then checking if I have back edges; the other is by counting Vs and Es and checking if |E| = |V| - 1, if that's true then the graph is a tree and there's no node we can delete without disconnecting it.

Both of the previous approaches solve the problem, but both need O(|E|+|V|), and the book says there's a faster way(that's probably a greedy approach).

Can I get any hints, please?

EDIT: More specifically, this is my question; given a connected graph G=(V,E), can I remove some edge e in E and have the resulting graph still be connected?

Answer 1

Any recursive traversal of the graph, marking nodes as they're visited and short-circuiting to return true if you ever run into a node that is already marked will do the trick. This takes O(|V|) to traverse the entire graph if there is no edge that can be removed, and less time if it stops early to return true.

edit

Yes, a recusive traversal of the entire graph requires O(|V|+|E|) time, but we only traverse the entire graph if there are no cycles -- in which case |E| = |V|-1 and that only takes O(|V|) time. If there is a cycle, we'll find it after traversing at most |V| edges (and visiting at most |V|+1 nodes), which likewise takes O(|V|) time.

Also, obviously when traversing from a node (other than the first), you don't consider the edge you used to get to the node, as that would cause you to immediately see an already visited node.

Answer 2

You list all edges E and take an edge and mark one by one the two end vertices visited. If during traversing we find that the two vertices have been visited previously by some edges and we can remove that edge.

We have to take edges at most |V| time to see whether this condition satisfy.

Worst case may go like this, each time we take an edge it will visit atleast new vertex. Then there are |V| vertices and we have to take |V| edges for that particular edge to be found.

Best case may be the one with |V| / 2 + 1 e