I'm reading Richard J. Trudeau's book "Introduction to Graph Theory", in page 54 it listed out the number of non-isomorphic graphs, given vertices $v$:
V: number of graphs
1: 1
2: 2
3: 4
4: 11
5: 34
6: 156
7: 1,044
8: 12,346
9: 308, 708
Then in exercise 27 it asks:
In the table on page 54, 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? If the table were continued, do you think more odd numbers would turn up in the second column?
I'm a bit lost here. There number of $v$ vertices graphs (in the sense of non-isomorphic) is quite huge and I don't see a way to determine if it's even or odd.
The key, i guess, is the self-complementary graphs. However, given vertices number $v$, there might be multiple self-complementary graphs, e.g. $v=5$ has 2.
Pls enlighten me.