Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

migrated from 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

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|cite|improve this answer

Your Answer


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