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.