What is the number of cyclic graphs with $n$ vertices and how to enumerate them?
For example, let the vertices be labeled as $A,B,\dots$. Then,
there is 1 circular graph of three vertices, with edges $\{(A,B), (B,C), (A,C)\}$, and
there are 3 circular graphs of four vertices, with edges $\{(A,B), (B,C), (C,D), (A,D)\}$, $\{(A,C), (B,C), (B,D), (A,D)\}$, or $\{(A,B), (B,D), (C,D), (C,A)\}$.
How many circular undirected simple graphs $C_n$ are there in general with $n$ vertices? Moreover, how can the sets of edges of such graphs be enumerated?
$\endgroup$1 Answer
$\begingroup$There are $\frac{(n-1)!}{2}$ labelled cycles. This is because, starting from vertex $A$ you can list the other vertices round the cycle in $(n-1)!$ different ways (all possible orderings of $n-1$ things), but this counts every cycle twice, because you can go around the cycle in either direction.
$\endgroup$ 3
