2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – Peter Oct 15 '14 at 10:26
  • $\begingroup$ 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? $\endgroup$ – Peter Taylor Oct 15 '14 at 10:28
  • $\begingroup$ No, I mean the number of all graphs. The sequence starts with $1,1,2,4,11,34,156,1044,12346$ $\endgroup$ – Peter Oct 15 '14 at 10:30
  • $\begingroup$ Ah, it doesn't have simple in the title so my search didn't find it. Thanks for adding the link. $\endgroup$ – Peter Taylor Oct 15 '14 at 10:32
  • $\begingroup$ 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. $\endgroup$ – Casteels Oct 15 '14 at 12:21
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.