The number of cyclic graphs with $n$ vertices and how to enumerate them

combinatoricsgraph theory

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?

Best Answer

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.

Related Question