The number of all pairwise non-isomorphic graphs

Question

How to prove that if $n = 4k + 2$ or $n = 4k + 3$, then the number of all pairwise non-isomorphic graphs with n vertices is even.
Any ideas on how to do this?

Answer 1

Fix a vertex set $V$ with $|V|=n$, where $n=4k+2$ or $n=4k+3$, for some nonnegative integer $k$.

Then $n(n-1)$ is even but not a multiple of $4$, hence ${\large{\binom{n}{2}}}$ is odd.

For any graph $G=(V,E)$, the isomorphism type of the complementary graph $G'=(V,E')$ is uniquely determined by the isomorphism type of $G$, and we have $$ |E|+|E'|=\binom{n}{2} $$ hence, since ${\large{\binom{n}{2}}}$ is odd, we get $|E|\ne|E'|$.

It follows that the graphs $G,G'$ are not isomorphic to each other.

Thus, the isomorphism types for graphs with vertex set $V$ come in pairs.

It follows the number of pairwise non-isomorphic graphs with vertex set $V$ is even.

Answer 2

Hints:

• Most graphs on $n$ vertices have a complement graph which they are not isomorphic to
• How many edges does a self-complement graph on $n$ vertices have?
• When it that not an integer?