Negative Space Graphs
Haskell, 72 bytes

f n=[(a,b)|b&lt;-[1..n],a&lt;-[1..b-1],mod n 4&lt;2,mod(a+b+sum[b|odd n,a&lt;2])4&lt;2]

Try it online!
A belated improvement inspired by ideas from kops. Takes vertex 1 to the the special vertex in the \$n=1 \bmod 4\$ case, rather than vertex n.

Haskell, 77 bytes

f n=[(a,b)|b&lt;-[1..n],a&lt;-[1..b-1],mod n 4&lt;2,mod(a+(last$b:[a|odd n,n==b]))4&lt;2]

Try it online!
This uses an easy-to-compute explicit criterion to decide whether an edge (a,b) belongs in the graph. Instantiates this algorithm, with the permutation cycling among the values modulo 4
4*m -&gt; 4*m+1 -&gt; 4*m+2 -&gt; 4*m+3 -&gt; 4*m

We include edges whose two endpoint vertices add to 0 or 1 modulo 4. Note that cycling vertices as per this permutation adds 2 modulo 4 to the vertex sum on each each, and so swaps edges and non-edges. This gives a permutation of vertices that complements the edges.
If the graph has an extra node beyond a multiple of 4, it is put in a cycle alone. We include edges with it when then other vertex is even. Permuting the vertices flips the parity, and so the graph remains self-complementary.
If the number of vertices isn't 0 or 1 modulo 4, no self-complementary graph is possible because there's an odd number of edges in the complete graph
Overall, here are the conditions:

If the input n isn't 0 or 1 modulo 4, output an empty list
Otherwise if n is even, include all edges (a,b) with a&lt;b and a+b equal to 0 or 1 modulo 4.
Otherwise if n is odd, do the same, but instead include edges of the form (a,n) when a is even.

The code combines the second and third cases by replacing the condition mod(a+b)4&lt;2 with mod(a+a)4&lt;2 when both odd n and b==n.