# What is the longest cycle of this digraph?

Here's the diagram from my book:

I eliminated the vertices one at a time until I came up with my solution of $<b, c, g, f, d, b>$, but the book presents a cycle of equal length: $<d, b, c, g, f, d>$.

Now, observing those two cycles, they involve the same points, but they start and end at different vertices. Moreover, they're both the same length...

So is there in fact no cycle that is longer than any other, or are these two cycles the same (and therefore the longest), even though they start and end at different vertices?

• I would say that they are both the same as my personal favourite $\langle c,g,f,d,b,c\rangle$ because you can get to one from another by a cyclic permutation. ;) Jul 18, 2017 at 19:07

• Importantly, the two cycles have not just the same vertex set, but have the vertices in essentially the same order (except that we have written one as beginning and ending at $b$, the other as beginning and ending at $d$). Jul 18, 2017 at 22:23
Ravi's comment alludes to the fact that both $\langle b,c,g,f,d,b \rangle$ and $\langle d,b,c,g,f,d \rangle$ are just different ways of writing the same cycle, namely the cycle obtained from the blue arrows in this modification of your diagram:
Importantly, both $\langle b,c,g,f,d,b \rangle$ and $\langle d,b,c,g,f,d \rangle$ use not only the same set of vertices, but also the same arrows, which is why we consider them to be the same cycle.