1
$\begingroup$

Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?

Looks to me likes its true ,is it?

$\endgroup$

migrated from cstheory.stackexchange.com Feb 4 '13 at 0:19

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Do you mean there is only one simple cycle in the graph? Or there can be more? $\endgroup$ – Paresh Feb 4 '13 at 14:48
1
$\begingroup$

No, it is not true. Consider the graph with vertices 1, 2, 3, 4, 5, 6 and edges 12, 23, 34, 45, 46, 56, 61. The dfs starting at vertex 1 yields two back egdes for the cycle (1,2,3,4,6).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy