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

Solution 1:

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

Solution 2:

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.