Proof that any self-complementary graph has to have $4k$ or $4k+1$ vertex, for some $k \in \mathbb N$

I've seen looking on previous questions that using this algorithm, I can construct self-complementary graphs.

I got confused at this point, because I'm not sure if I should proof that there are no graphs with $4k+2 $ or $4k+3$ vertex, in witch case the algorithm doesn't seem to be very helpful.

Is this enough to proof that the graph has to have $4k$ or $4k+1$ vertex?

Solution 1:

That's a classic result and it's even on Wikipedia.

If $G$ is self-complementary, then its edges contain half of all of the possible edges (and the complement has the others). Thus if $G$ has $n$ vertices, its number of edges is

$$ \frac{{n \choose 2}}{2} = \frac{n(n - 1)}{4} $$

Thus $n$ or $n - 1$ must be a multiple of $4$ (I'm pretty sure you can figure that out if needed). That is, $n = 4k$ or $n = 4k + 1$ for some $k$.