Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 3 down vote accepted

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.

share|cite|improve this answer
>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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.