Soppose we have an udirected, connected graph. Apply the DFS algorithm to find back edges of this graph. Now, I have found a lecture notes saying following :

Each back edge (i,j) defines a cycle. A cycle consists of the back edge (i,j) and unique tree edges forming the path from j to i. The cycles so defined by the back edges form a cycle base of the graph. Every cycle of the graph is the union (exclusive OR) of two or more cycles from this cycle base.

Can I conclude from this that every simple cycle in this graph will contain at least one back edge?

  • 1
    $\begingroup$ Considering that trees don't have cycles, yes you can. $\endgroup$ – Karolis Juodelė Dec 23 '13 at 8:25

Your Answer

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

Browse other questions tagged or ask your own question.