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?
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.
We use cookies to ensure that we give you the best experience on our website. If you continue to use this site we will assume that you are happy with it.OkRead more