find all self-complementary graphs on five vertices

I know that the two complements should have an equal number of edges, namely $\binom{5}{2}/2=5$. Since there are 10 possible edges, there are at least $\binom{10}{5}/2=126$ possible pairs of graph-complement pairs.

But after making drawings for the same problem with four vertices, I know many of them are isomorphic and can be obtained from by rotations and reflections.

How should I proceed in eliminating these isomorphic graphs?

In the first place, am I taking the right approach, or is their a more effective solution?


The sum of degrees is $10$, and since the graph is self complementary, by symmetry the degree sequence must be

$$(d_1,d_2, 2,4-d_2,4-d_1) \,,$$

where $d_1, d_2 \in \{ 0,1,2 \}$, and $d_1 \leq d_2$.

It is easy to see that $d_1=0$ is not possible, since then the last degree would be $4$, thus $d_1, d_2 \in \{ 1,2 \}$, and $d_1 \leq d_2$.

Case $1$ $d_1=1, d_2=1$. Your degree sequence is $(1,1,2,3,3)$. Each of the vertices of degree $3$ must be connected to all vertices excluding one end vertex. There is only one graph up to isomorphism.

Case $2$ $d_1=1, d_2=2$. Your degree sequence is $(1,2,2,2,3)$. You have two graphs here: the end vertex is connected to a degree $2$ or $3$.

Case $3$ $d_1=2, d_2=2$. Your graph is connected (why?) and has all degrees $2$. Only 1 possibility.


Non-isomorphic 5-edge 5-vertex graph representatives are drawn below with their non-edges in orange (generated using geng 5 5:5, which comes with Nauty):

enter image description here

We include the degree sequences below the graphs.

We can eyeball these to see which are self-complementary: the bottom-left and bottom-right.

Of the four possibilities given in N.S.'s answer, only two are self-complementary, which we can redraw:

enter image description here