# Finding total amount of permutations between edges and nodes in a cycle

I am interested in the graph theory/combinatorics problem:

if you have a cycle, how many ways can you rearrange the edges and nodes such that you still only have one cycle?

any discussion is welcome

To state it another way

If the graph itself was simply one large cycle, how many ways could I rearrange the edges while maintaining a single cycle? Only one incoming and outgoing edge per node and therefore the length of the cycle must be the same with each permutation.

nodes are marked edges are not.

Does that may things clearer?

• Are you asking about rearranging a graph without touching that specific cycle? (Otherwise the fact it had a cycle originally means nothing more than a min length requirement) Jan 21 '13 at 23:59
• If the graph itself was simply one large cycle, how many ways could I rearrange the edges while maintaining a single cycle? Only one incoming and outgoing edge per node and therefore the length of the cycle must be the same with each permutation. Does that may things clearer? Jan 22 '13 at 0:08
• Yes, are both the edges and nodes marked? Jan 22 '13 at 0:14
• nodes are marked edges are not Jan 22 '13 at 0:14

If you have a cycle graph with $N$ nodes and edges, you can permute the nodes among themselves in $N!$ ways, without altering the shape (Is the word here topology?).
But as this results in similar graphs up to rotation, you should either treat it as holding a node constant and performing the permutation on the remaining $N-1$ nodes for a $(N-1)!$ result or simply divide the previous result by $N$ for there are this many equivalence classes.
• Ah my bad, should've held one node as a constant permuting the remaining $N-1$ or simply divide the result by $N$ as there are N equivalent classes. I'll fix it, sorry. Jan 22 '13 at 0:29