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

Question

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 ?

Answer 1

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...)