1
$\begingroup$

Here's the diagram from my book:

enter image description here

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. ;) $\endgroup$
    – Arkady
    Jul 18, 2017 at 19:07

2 Answers 2

2
$\begingroup$

I suppose it would depend on how you define 'same'. But for most purposes, I would say they are the same, after all, it is the same set of objects. It's like, are Alfred and Bob the same two people as Bob and Alfred? Of course, if for some reason the starting point did matter, than in that situation it would not be the same. I think the definition depends on the scenario, but in this one, they mean the same thing.

$\endgroup$
1
  • 1
    $\begingroup$ 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$). $\endgroup$ Jul 18, 2017 at 22:23
1
$\begingroup$

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:

Diagram with cycle edges highlighted

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.

$\endgroup$
0

Your Answer

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

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