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 ?
 A: 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...)
