How many vertices can a self-complementary graph have?

Question

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true?

What I know: Paley graphs are self-complementary, so if $n$ is congruent to 1 mod 4 and is a prime power, then there is a self-complementary graph on $n$ vertices. Also, the set of $n$ such that there is a self-complementary graph on $n$ vertices is closed under products. Together (since there is a self-complementary graph on 4 vertices) these imply that if the prime factorization of $n$ has even number of 2s and an even number of every prime congruent to 3 modulo 4 then there is a self-complementary graph on $n$ vertices.

Answer 1

Note that if $G$ be a self-complementary graph with $n$ vertices, then the following gives a self-complementary graph $H$ on $n+4$ vertices: Let $H$ be the graph obtained by adding 4 new vertices $\{a,b,c,d\}$ to $G$, with edges $(a,b),(b,c),(c,d), (a,x), (d, x)$ for any vertex $x$ of $G$.

Why $H$ is self-complementary? As $G$ is self-complementary, there is a permutation $f:V(G)\to V(G)$ such that, for any $u,v$ distinct vertices of $G$, $(u,v)$ is an edge in $G$ if and only if $(f(u),f(v))$ is not an edge in $G$. We can define $g:V(H) \to V(H)$ by $g(a)=b; g(b)=d; g(c)=a; g(d)=c$ and $\left. g\right|_{V(G)} = f$, and it is easy to see that $g$ is an isomorphism between $H$ and its complement.

As there are self-complementary graphs on $1$ vertex and on $4$ vertices, it follows that, for any $n=0,1\quad (mod 4)$ there is a self-complementary graph on $n$ vertices.

Answer 2

Quoting an answer I posted some time ago on MathSE:

Take a complete graph with vertex set $V$ and edge set $E={V\choose2}$. Let $\alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. Of course, such permutations exist if and only if $|V|\equiv 0$ or $1\pmod 4$. (N.B. The word "cycle" is used here in its group theory sense, not its graph theory sense!)

Let $\beta$ be the permutation of $E$ induced by $\alpha$. Observe that $\beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph consisting of the black edges is self-complementary; the permutation $\alpha$ is an isomorphism between the black graph and the white graph.

Example. To construct self-complementary graphs of order $5$, take $V=\{a,b,c,d,e\}$ and let $\alpha=(a\;b\;c\;d)(e)$ so that $\beta=(ab\;bc\;cd\;ad)(ac\;bd)(ae\;be\;ce\;de)\;$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the bull graph.

An alternative proof is often given in graph theory textbooks, e.g., quoting Exercise 1.1.31 on p. 17 of Douglas B. West's Introduction to Graph Theory, second edition:

Prove that a self-complementary graph with $n$ vertices exists if and only if $n$ or $n-1$ is divisible by $4.$ (Hint: When $n$ is divisible by $4,$ generalize the structure of $P_4$ by splitting the vertices into four groups. For $n\equiv1$ mod $4,$ add one vertex to the graph constructed for $n-1.$)