# 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) – Guest 86 Jan 21 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? – user1340048 Jan 22 at 0:08
Yes, are both the edges and nodes marked? – Guest 86 Jan 22 at 0:14
nodes are marked edges are not – user1340048 Jan 22 at 0:14

## 1 Answer

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.

-
This overcounts the possibilities because a cycle can be rotated without giving a different graph. Hanging our hats on the OP's commment (not entirely consistent with how the question is asked) that "nodes are marked[;] edges are not", one wants a count of permuting "the nodes among themselves" that gives distinct cycles. – hardmath Jan 22 at 0:20
hardmath, that is exact what I want. How many distinct cycles can I obtain. – user1340048 Jan 22 at 0:22

1
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. – Guest 86 Jan 22 at 0:29
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 7, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9415320754051208, "perplexity_flag": "middle"}