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
    
Do you mean there is only one simple cycle in the graph? Or there can be more? –  Paresh Feb 4 '13 at 14:48
add comment

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.

1 Answer

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
add comment

Your Answer

 
discard

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