Quoting [an answer I posted some time ago on MathSE](https://math.stackexchange.com/questions/40745/constructing-self-complementary-graphs/412930#412930):

> 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!]  
<br>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.]  
<br>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 one that looks like the letter A.

**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.$)