find all self-complementary graphs on five vertices

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.

Tags:

Graph Theory