# Math Help - Complements and Isometries

1. ## Complements and Isometries

Show that if a simple graph G is isomorphic to its complement $\overline{G}$, then G has either 4k or 4k+1 vertices for some natural number k.

2. Originally Posted by meggnog
Show that if a simple graph G is isomorphic to its complement $\overline{G}$, then G has either 4k or 4k+1 vertices for some natural number k.
In any simple graph the number of vertices will be $|V|=4k,~4k+1,~4k+2,\text{ or }4k+3$. WHY?
In a self complementary graph the number of edges in $G$ must be same as the number of edges in $\overline{G}$. WHY?

For which of the possible $|V|$ is $\dbinom{|V|}{2}$ even?