0
votes

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?

1

1 Answers

1
votes

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.