Self - complementary graphs with up to 7 vertices

Question

How could I find all the self complementary graphs with 7 vertices at most? Is there an algorithm that produces self-complementary graphs?

Answer 1

The only one's you can find are: 1 vertix, 4 vertices: 2-2-1-1 degrees, 5 vertices: 3-2-2-2-1 , 2-2-2-2-2 For 2,3,6,7 vertices, graphs are not self-complementary as if you devide their edges with 2, the number you get is odd.

Answer 2

As Amy says, you need the number of edges of $G$ to be half the number of possible edges, i.e. $n(n-1)/4$. So this has to be an integer, which requires $n\equiv 0,1\pmod 4$.

For $n=4$ your degree sequence has to add up to $6$, and for $n=5$ to $10$. It has to be symmetrical - there are the same number of degrees $k$ as $n-1-k$ for each $k$. Since you can't have both a vertex connected to everythin and one connected to nothing, you can't have degrees $0$ or $n-1$.

For $n=5$ this gives one possible sequence $2,2,1,1$ and it's easy to see there is only one graph with this sequence. For $n=5$ the options are $2,2,2,2,2$ or $3,2,2,2,1$ or $3,3,2,1,1$. The first and third of these both have exactly one possible graph. However, the sequence $3,2,2,2,1$ can't give a self-complementary graph. The two vertices of high and low degree swap over when we take the complement, and this means if they are adjacent in $G$ they are non-adjacent in $\overline{G}$.