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?
The number of all pairwise non-isomorphic graphs
discrete mathematicsgraph theorygraph-isomorphism
Best Answer
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.