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