Detect if there exists a cycle in an undirected gr

Question

My question is concerned with DETECTING if there exists a cycle. I don't care where the cycle occurs but only if there exist a cycle. In particular, I am working on the implementation of a (maximally) spanning tree algorithm. I have sorted the edges in descending order and then I pick one edge at the time and put it in the set of the graph edges IFF it doesn't cause a cycle.

I have found out that for undirected graphs in only enough to check if no_of_edges > no_of_vertices - 1. Is this right? I am trying to find a case when this is not true bt I cannot. Of course this doesn't imply that this is correct.

Thanks

Answer 1

Just run DFS search; it automatically detects loops because that's the stopping condition for DFS --- you stop when you enter a node that's already in a stack, and that's when you have found a cycle.

Answer 2

If the graph is disconnected, or more than one edge is between two given nodes, then your idea fails. If you stipulate that there is at most one edge between any two nodes, then you still have to check for connectedness.

But yes, if number of edges <= number of vertices-1 in a connected graph, then there can be no cycles.

Answer 3

Basically speaking your idea is correct. But there may be some pitfalls:

1) First run a DFS and find all connected components, check whether the condition no_of_edges <= no_of_vertices - 1 in all connected components.

2) Check whether each connected component contains multiple edges.