CODEWITHSUNDEEP
graphtreegraph-algorithmshortest-pathdepth-first-search
user4556130
user4556130

Reputation:

Number of Edges and Cycle Detection?

I ran into a challenging question: When we know the Number of Edges, in O(|V|) and not O(|V|+|E|), we can detect whether a simple undirected graph has a cycle or not.

I know there is an O(|V|) algorithm for finding out whether a cycle exists or not. But the above sentence says, with knowing number of edges?!! anyone could describe it's true or false?

Upvotes: 1

Views: 991

Answers (1)

colavitam
colavitam

Reputation: 1322

In an undirected graph, if the graph is connected and there are more edges than are needed to make the graph connected, it contains a cycle. In other words, a graph of V vertices requires V-1 edges to be connected. Any additional edges must connect two vertices that are already in the same component, thereby creating a cycle.

In other words, if the graph contains more than V-1 edges, it contains a cycle.

Upvotes: 1

Related Questions