I'm seeing seemingly contradictory information about this around. On the one hand, it seems that for undirected graphs, you need at least 3 nodes to make a cycle. On the other other, I've also seen people differentiate between trivial and non-trivial cycles.

Let's say in your directed graph you have two nodes A and B with an edge from A to B and an edge from B to A. Do you have a cycle (A, B)? And does it always count as a cycle, or would some people consider it a cycle and others not?

Also, let's say you traverse that directed graph and hit A before you hit B. Is the edge (B, A) a back edge?


1 Answer 1


Like most things, you should only care about definition if it makes sense and useful in your context.

And in the context of strongly connected component, a nice property we would like to say is that:

Node $a$ and $b$ belongs to the same cycle if and only if $a$ and $b$ are strongly connected.

Graph with strongly connected components marked

This nice statement only holds if you count $f\rightarrow g\rightarrow f$ as a cycle. So, we would like to count this as a cycle when talking about strongly connected components.

  • $\begingroup$ That makes sense, thanks for explaining. $\endgroup$ Commented Feb 12, 2017 at 0:21
  • $\begingroup$ Weird. This is simpler than I thought it would be. $\endgroup$
    – wogsland
    Commented Feb 12, 2017 at 4:17

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.