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?
Best Answer
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$.