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?

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

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.