# 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?

-

## 1 Answer

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.

-
>Your graph is connected (why?) Because the graph reduces to (2,2,2,2,2) -> (1,1,2,2,2) -> (1,1,1,1). Hence, (2,2,2,2,2) is a graphical sequence. Or more simply, the graph is C5. Was this your intended answer? –  user81055 Jun 5 '13 at 21:22
My intention was connected implies $C_5$. Why is your graph $C_5$ then? ;) –  N. S. Jun 6 '13 at 2:03
Actually I can't explain why; can you help me? I began with assuming G was not $C_5$ and had degree sequence (2,2,2,2,2). I want to say G is not connected, but I don't know how. –  user81055 Jun 6 '13 at 12:32
@user81055 Assume by contradiction that $G$ is disconnected. Then one component must have at most two vertices. But then the vertices cannot have degree 2. –  N. S. Jun 6 '13 at 13:38