A few doubts regarding graph theory:

  1. When considering cycles in a connected graph, we have cycles that go both clockwise and anti-clockwise. Do we consider these as two separate cycles?

  2. In a complete graph such as $K_3$, how many Hamiltonian cycles exist? My guess is that it is $3!$ because each vertex connects to every other vertex and any permutation of the vertices gives you a cycle. But when I look it up online, it says there are only 2. How and why?

  3. Consider simple cycles, not Hamiltonian or Eulerian. Am I right if I say that $K_3$ has $3!$ simple cycles?


You can come up with several different definitions for what a "cycle" is. The definition that gives you two cycles in a triangle is the following:

A cycle is a cyclic sequence of at least 3 vertices $v_0,\ldots,v_{n-1}$ such that $v_i$ is connected to $v_{i+1 \pmod{n}}$.

Here a "cyclic sequence" is a sequence up to rotations but not up to reflection. Under this definition, the two orientations of a cycle are considered different cycles. In other contexts you might want to allow reflections as well, and then the two orientations are equivalent. In most contexts these niceties don't really matter, and if they do, you should explain exactly what you mean by cycle.

The two cycles in the complete graph on $\{1,2,3\}$ according to this definition are $1,2,3$ and $1,3,2$; note $1,2,3=2,3,1=3,1,2$ and $1,3,2=3,2,1=2,1,3$.

Sometimes it makes sense to consider sequences not up to rotation, and then you indeed get $3!$ cycles in $K_3$. It all depends on your definition - use whatever is most convenient for you.


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.