CODEWITHSUNDEEP
graphdepth-first-searchedgesundirected-graph
ryekos
ryekos

Reputation: 162

Cycle in undirected graph without tree edges?

In an undirected graph, for which DFS has been executed (in order to generate a DFS tree and thus categorize every edge as either tree edge or back edge), can there be cycles in the graph that only consist of back edges, i.e. no tree edges?

Upvotes: 0

Views: 108

Answers (1)

templatetypedef
templatetypedef

Reputation: 372972

Sure. Take a large clique, for example. Deleting a single DFS tree from a clique leaves a huge number of edges and consequently a lot of cycles.

Upvotes: 1

Related Questions