How many connected and undirected graphs are there when d(v) = 2 for every vertex in the graph.

Question

Well, at the beginning I thought the answer would be (n-1)! But it's not correct.

My assumption to that answer was that its just like putting n people in a circle, but it doesnt seem like its exactly the same problem.

Answer 1

If a connected graph is 2-regular, then it is a cycle. So your question is how many cycle graphs exist on the $n$ vertices $\{1,\ldots,n\}$. The number of unlabeled cycle graphs on $n$ vertices is of course 1.

The number of labeled cycle graphs on $n$ vertices can be shown to equal $(n-1)! /2$. Pick the first vertex, without loss of generality, to be the vertex 1. As you correctly pointed out in the comment above, the neighbors $\{a,b\}$ of vertex 1 can be chosen in ${{n-1} \choose 2} = (n-1)(n-2)/2$ ways. Put these two vertices in lexicographic order. Say $a < b$, so we'll continue next with choosing the remaining neighbor of $a$. This vertex $c$ can be chosen in $n-3$ ways. The remaining neighbor of $c$ can be chosen in $n-4$ ways, and so on. Thus, all the vertices of the cycle can be chosen in $(n-1)(n-2)/2 \times (n-3)! = (n-1)!/2$ ways.

Another way to obtain the value is as follows. The symmetric graph $S_n$ acts on the vertex set $V=\{1,2,\ldots,n\}$ of the graph, and there is an induced action on the set of subsets $\mathcal{G}$ of $V$. Each subset of $V$ corresponds to a unique labeled graph. We want to find the number of elements in the orbit of the cycle graph $\{ \{1,2\}, \{2,3\}, \ldots, \{n,1\} \}$ under the action of $S_n$ on $\mathcal{G}$. The stabilizer of this graph is its automorphism group, which is the dihedral group of order $2n$. By the orbit-stabilizer lemma, the size of the orbit equals the index of the stabilizer, which is $n! / 2n = (n-1)!/2$.