# Is there a reason why the number of non-isomorphic graphs with $v=4$ is odd?

I am working through Trudeau’s Introduction to Graph Theory, which contains the following problem:

In the following table, the numbers in the second column are mostly even. If we ignore the first row on the ground that $v=1$ is such a trivial situation that its uniqueness is unremarkable, that leaves $v=4$ as the only number of vertices listed for which there are an odd number of graphs. Do you think this is due to chance, or can you think of some reason why $v=4$ should be unique?

 v    number of non-isomorphic graphs
1            1
2            2
3            4
4           11
5           34
6          156
7        1,044
8       12,346
9      308,708


Note, this problem concerns the number of non-isomorphic graphs.

Here’s what I have so far:

The maximum number of edges in a graph with $v=4$ is $\max(e)=\frac{1}{2}(v)(v-1)=\frac{1}{2}(4)(3)=6$. The graphs with $e=0,1,2,4,5,6$ come in pairs because each graph has a complement. So, there are an odd number of graphs with $v=4$ iff there are an odd number of graphs with $v=4$ and $e= \frac{\max(e)}{2}$.

There are 3 graphs with $v=4$ and $e= \frac{\max(e)}{2}=3$, so therefore there is an odd number of graphs with $v=4$.

However, I don’t understand why $v=4$ should be special in this regard, even though it feels special.

#### Solutions Collecting From Web of "Is there a reason why the number of non-isomorphic graphs with $v=4$ is odd?"

Definition:
Let $g(n)$ denote the number of unlabeled graphs on $n$ vertices, let $e(n)$ denote its $2$-part, that is the largest power of $2$ which divides $g(n)$.

Lemma: If $n\geq5$ is odd then $e(n) = (n+1)/2-\lfloor \log_2(n) \rfloor$. If $n \geq 4$ is even then $e(n) \geq n/2 – \lfloor \log_2(n) \rfloor$ with equality iff $n$ is a power of $2$.

Corollary: The amount of unlabeled graphs is even for $n > 4$

Some values $e(\{4,5,\ldots,15\})=\{0,1,1,2,1,2,2,3,3,4,4,5\}$ (for even numbers it is the lower bound).

The theorem is due to Steven C. Cater and Robert W. Robinson and can be found, including a proof, in this publication.

They mention that $g(n)$ is not only even but contains a large number $2$’s in its prime factorisation for large $n$ (this also follows form the formula). In fact they even show that they are asymptotically $n/2$ factors of $2$ in $g(n)$.

If a graph on $n$ vertices has $e$ edges, then the number of edges in its complement is
$$\frac{n(n-1)}{2} – e.$$
So if if $n(n-1)/2$ is odd we can divide graphs in pairs (graph,complement),
and then the number of graphs must be even. In particular the the parity of the number of
isomorphism classes of graphs is equal to the parity of the number of isomorphism
classes of self-complementary graphs. When $n=4$, the path is the unique self-complementary graph and the number of isomorphism classes is odd.
Clearly when $n=6$ or $n=7$ there must be an even number of isomorphism classes self-complementary graphs.