# How many ways can $N$ edges be added to a labeled cycle graph with $2N$ vertices to produce a simple cubic graph?

Equivalently, how many functions on the set $\{0, 1, 2, ..., 2N-1\}$ satisfy the following conditions?

1. For all $n$, $f(n) \neq n$.
2. For all $n$, $f(n) \neq n+1 ~(\text{mod } 2N)$.
3. For all $n$, $f(f(n)) = n$.

If the answer to this question is denoted $F(N)$, I've determined that $F(2) = 1$, $F(3) = 4$, and $F(N) \le \frac{(2N-3)(2N-3)!}{2^{N-2}(N-2)!}$. (Note that the answer is $\frac{(2N)!}{2^N N!}$ if you remove condition 2.) But I don't know how to determine a general solution for $F$.

-
Could you please point out, how this relates to graphs? –  draks ... Apr 24 '12 at 6:37
@draks : In a cycle graph, each vertex is connected to two other vertices. To make the graph cubic, we need to add one edge to each vertex. The function $f$ maps each vertex to the vertex that this new edge connects it to. Condition 3 says that the graph is undirected, so that if a new edge connects $v$ to $w$, it also connects $w$ to $v$. Condition 2 says that the new edges don't replicate existing edges. Condition 1 says that a new edge never connects a vertex to itself. –  Will Orrick Apr 26 '12 at 17:41

You can use the principle of inclusion-exclusion. Let $s(i_1,i_2,\ldots,i_k)$ denote the number of ways to partition $2N$ vertices into $N$ unordered pairs if $\{i_1,i_1+1\}$, $\{i_2,i_2+1\}$, ..., $\{i_k,i_k+1\}$ (with arithmetic performed mod $2N$) are required to be among the pairs. Observe that this quantity is zero if $i_k=i_j+1 \pmod{2N}$ for any $j$, $k$, since $\{i_j,i_j+1\}$ and $\{i_j+1,i_j+2\}$ cannot both be pairs. Then the number of partitions in which none of the pairs are edges of the cycle graph is $$s()-\sum_i s(i)+\sum_{i<j}s(i,j)-\sum_{i<j<k}s(i,j,k)+\ldots.$$
Now if $s(i_1,i_2,\ldots,i_k)$ is nonzero then it equals $\dfrac{(2N-2k)!}{2^{N-k}(N-k)!}=(2N-2k-1)!!$ since the pairings are fixed for $2k$ of the vertices, which leaves $2N-2k$ vertices to pair up. The number of ways of choosing $\{i_1,i_2,\ldots,i_k\}$ so that $i_k\ne i_j+1\pmod{2N}$ holds for all $j$, $k$, is $\binom{2N-k}{k}+\binom{2N-k-1}{k-1}$. (This is the same as the number of words that can be formed from $k$ Ps and $2N-2k$ Ss or from $k-1$ Ps and $2N-2k$ Ss. Here P stands for "pair" and S stands for "singleton". The word PPSPS, for example, corresponds to the $\{i_1,i_2,i_3\}=\{0,2,5\}$. The $i_j$ are the positions of the Ps, with Ps thought of as occupying two sites and Ss as occupying one. The first binomial coefficient counts the $\{i_1,i_2,\ldots,i_k\}$ in which none of the $i_j$ equals $2N-1$; the second counts the $\{i_1,i_2,\ldots,i_k\}$ in which one of the $i_j$ equals $2N-1$.)
Putting this all together, the number of partitions in which none of the pairs are edges of the cycle graph is $$\sum_{k=0}^N(-1)^k(2N-2k-1)!!\left[\binom{2N-k}{k}+\binom{2N-k-1}{k-1}\right].$$ For $N=1,2,3,4,\ldots$ we get 0, 1, 4, 31, 293, 3326, 44189, 673471, 11588884, 222304897. This is A003436 in the Online Encyclopedia of Integer Sequences, which contains many useful references about this sequence.