# Number of unlabeled simple graphs with $n$ nodes even for all $n\ge 5$?

The extended version of OEIS for the number of unlabeled simple graphs with $n$ nodes shows that the only odd number (besides the trivial cases $n = 0$ and $n = 1$) is for $n=4$ ($11$ graphs). The list goes upto $n=75$, so my conjecture is that $11$ is the last odd number in the list.

• Is the number of graphs with $n$ nodes even for all $n\ge 5$ ?

• If yes, is there an easy proof for this property ?

• It would be enough to prove that the number of self-complementary graphs for all $n\ge 5$ is even. Such graphs only exist for $n=4k$ or $n=4k+1$ – Peter Oct 15 '14 at 10:26
• Are you referring to A005470 (in which case you seem to be missing the very important word planar from the question) or to a different sequence? – Peter Taylor Oct 15 '14 at 10:28
• No, I mean the number of all graphs. The sequence starts with $1,1,2,4,11,34,156,1044,12346$ – Peter Oct 15 '14 at 10:30
• Ah, it doesn't have simple in the title so my search didn't find it. Thanks for adding the link. – Peter Taylor Oct 15 '14 at 10:32
• An old paper by Read (On the number of self-complementary graphs and digraphs. J. London Math. Soc. 38 1963 99–104.) gives explicit formula for the number of self-complementary graphs. (see Formulas (4) and (5) ) Unfortunately, they don't seem so easy to work with, but from the form of them (a sum of rationals with numerator a power of $2$) it certainly seems at least plausible that, for $n>4$, the number of them is even. – Casteels Oct 15 '14 at 12:21

## 1 Answer

The result which Casteels mentions in the comments is (for a graph with $n = 4N$)

$$\sigma_{4N} = \sum_{(k)} \frac{2^{P}}{\prod (4s)^{k_s} \cdot k_s!}$$

where $$P = 2 \sum_{s=1}^{N} s k_s^2 + 4\sum_{1\le\alpha<\beta\le N} k_\alpha k_\beta \ \textrm{gcd}(\alpha, \beta)$$ and the sum is over the cycle structure of permutations of $4N$ such that each cycle length is a multiple of 4. (Source: Clapham, C. R. J. An easier enumeration of self-complementary graphs. Proc. Edinburgh Mathematical Soc. (Series 2) 27.02 (1984): 181-183.).

$$\sigma_{4N} = \sum_{(k)} \frac{4^{\sum_{s=1}^{N} (s k_s^2 - k_s) + 2\sum_{1\le\alpha<\beta\le N} k_\alpha k_\beta \ \textrm{gcd}(\alpha, \beta)}}{\prod s^{k_s} k_s!} \\ = \sum_{(k)} 16^{\sum_{1\le\alpha<\beta\le N} k_\alpha k_\beta \ \textrm{gcd}(\alpha, \beta)} \prod_s \frac{4^{k_s(s k_s - 1)}}{s^{k_s} k_s!}$$

Given $x \in \mathbb{Q}$ we can define the "powers of two" function $t(x)$ by $x = 2^{t(x)} \frac{p}{q}$ where $p$ and $q$ are odd and $t(x) \in \mathbb{Z}$. Then

$$\begin{eqnarray}t\left(\frac{4^{k_s(s k_s - 1)}}{s^{k_s} k_s!}\right) & = & 2 k_s(s k_s - 1) - k_s\;t(s) - t(k_s!) \\ & \ge & 2k_s(s k_s - 1) - k_s\log_2 s - k_s \\ & = & k_s(2 s k_s - 3 - \log_2 s)\end{eqnarray}$$

This is positive except in the following cases:

• $k_s = 0$: not a concern.
• $k_s = 1, s = 1$: the bound is $-1$, but the actual value of $\frac{4^{k_s(s k_s - 1)}}{s^{k_s} k_s!} = 1$
• $k_s = 1, s = 2$: the bound is $0$, but the actual value of $\frac{4^{k_s(s k_s - 1)}}{s^{k_s} k_s!} = 2$

So for the product to be odd, we require that all of the $k_s$ are $0$ except that (possibly) $k_1 = 1$. If all of the $k_s$ are zero then the permutation is of zero elements; if they're all zero except $k_1 = 1$ then the permutation is of four elements. Therefore the number of self-complementary graphs with $n = 4N > 4$ is a sum of even numbers, and hence is even.

Clapham also states

The formula for $\sigma_{4N+1}$ is just the same as that for $\sigma_{4N}$, with $P$ replaced by $P'$, where $P' = P + \sum k_s$

so once we've eliminated the case $n=5$ we have the result you desire.

(I'm not sure that this counts as an easy proof, though...)