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