Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question

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.

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

1 Answer 1

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.