I have some graph $G$ and a list of vertices $(v_1, ..., v_N) \in V$. Using graph structures in Mathematica version 9.0, what is the most efficient way to determine whether or not $(v_1, ..., v_N)$ represents a cycle, and then, if so, to output a permutation cycle starting from some desired $v_i$?

Let me provide a specific example:

Say I have a ring of eight vertices where:

$v_1 \to v_2$

$v_2 \to v_3$

$v_3 \to v_4$

$v_4 \to v_5$

$v_5 \to v_6$

$v_6 \to v_7$

$v_7 \to v_8$

$v_8 \to v_1$

And also:

$v_2 \to v_4$

$v_4 \to v_6$

$v_6 \to v_8$

$v_8 \to v_2$

Say the above list is scrambled (i.e. we randomly assign the vertex labels). Without scrambling things here, and specifying that I want a permutation to start from $v_2$, how would I output a permutation:


Scrambling, we could maybe map the labels: $(v_1, v_2, v_3, v_4, v_5, v_6, v_7, v_8)$ to something like: $(v_{1111111111}, v_{11011}, v_{111110011}, v_{100101}, v_{11}, v_{1010111}, v_{111}, v_{101010101})$ where the labels convey no ordering information.


2 Answers 2


If I am reading your question correctly, you are looking for

HamiltonianGraphQ@Subgraph[g, {v1, v2, ...}]

You can use FindHamiltonianCycle to actually find a cycle (an ordering of vertices).

  • $\begingroup$ Please let me know if I misunderstood. $\endgroup$
    – Szabolcs
    Feb 11, 2013 at 19:47
  • $\begingroup$ Right, calling "FindHamiltonianCycle" solves my problem, though I have a special very easy case of what would otherwise by an NP-complete problem. I suppose I could also cut the connections between a pair of vertices $v_i$ and $v_j$ and then run "FindShortestPath". $\endgroup$ Feb 11, 2013 at 22:04
  • 1
    $\begingroup$ Note that FindHamiltonianCycle is not necessarily slow ("bad" complexity). It is slow for some input graphs, but it isn't for a cycle graph. $\endgroup$
    – Szabolcs
    Feb 11, 2013 at 22:08
  • $\begingroup$ I think I should be able to make my set of vertices a cycle... Do we know the time complexity for "FindHamiltonianCycle" on a cycle graph? $\endgroup$ Feb 11, 2013 at 22:53
  • $\begingroup$ @Roget I don't know how it is implemented, but it makes sense to assume that it is linear complexity (in the number of nodes). There aren't that many ways to traverse a cycle graphs. If you want to make sure, you can measure directly. $\endgroup$
    – Szabolcs
    Feb 11, 2013 at 23:12

If you just want to verify a given list of vertices is a cycle, you could define the following function to check it's cycle:

cycleQ[g_, vs_] :=
          edge = If[DirectedGraphQ[g], DirectedEdge, UndirectedEdge];
          VectorQ[Partition[vs, 2, 1, 1], EdgeQ[g, edge @@ #] &]

For example,

g = CycleGraph[10];

In[96]:= cycleQ[g, Range[5]]
Out[96]= False

In[97]:= cycleQ[g, Range[10]]
Out[97]= True

To permute the list, you could use RotateLeft or RotateRight with Position:

In[91]:= RotateLeft[{a, b, c, d, e}, 
             Position[{a, b, c, d, e}, d][[1, 1]] - 1]
Out[91]= {d, e, a, b, c}
  • $\begingroup$ Thanks, the CycleQ[...] function addresses the first part of my question! $\endgroup$ Feb 11, 2013 at 14:23
  • $\begingroup$ However, let's say the vertices are unordered and not necessarily just connected to their nearest-neighbors in the cycle (i.e. vertex $i$ could be connected to vertex $j$ and $j+1$, etc.). We are only guaranteed that there is a unique solution for the cycle that only uses each vertex once. How would we output a cycle permutation? $\endgroup$ Feb 11, 2013 at 14:24

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.