Given n vertices on a complete graph, I want to know how many distinct cycles can be formed that:
- Start at one vertex and end at the same vertex
- Never revisit a vertex besides the starting / ending vertex
- Two cycles that visit the same vertices with different starting / ending vertices are considered to be the same cycke.
- ex: A-B-C-A == B-C-A-B
- Two cycles that visit the same verticies but in opposite orders are consider the same
- A-B-C-A == A-C-B-A
- We only count cycles that visit three or more distinct verticies
A small example using vertices A, B, C, and D. The possible cycles are:
A-B-C-A
A-D-C-A
A-B-D-A
B-C-D-B
A-B-C-D-A
A-B-D-C-A
A-D-B-C-A
Is there a closed form formula for calculating how many cycles there are given just how many verticies there are in the graph,n?
I've gotten some leads here but haven't been able to find an answer yet. I'm struggling with how to account for all the cycles that we consider to be identical.
Counting according to cycle length $k$, we obtain $$\sum_{k=3}^n \binom{n}{k} \frac{(k-1)!}{2}$$ cycles in the complete graph $K_n$, and this is OEIS A002807.