Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Show that there exists a self-complementry graph of order $ n $ if and only if $ n = 0$ or $ 1 \ (\mbox{mod } 4) $.

My thoughts so far:

I've proven the 'only if' direction.

For the 'if' direction, I need to show that if $ n = 0$ or $ 1 \ (\mbox{mod } 4) $ then I can construct a self-complementary graph. I've started by focusing on the case $ n = 0 \ (\mbox{mod } 4) $; in particular, I've drawn such a graph in the case n = 4 (a Z shape). But I'm struggling to generalise my method to n = 8 and higher (in fact, I haven't successfully constructed a self-complementary graph of order 8). I'm not really sure how to think about this; I'm new to Graph Theory and so haven't had much practice yet. EDIT: I've had a further thought. The graph I construct must have exactly $ \frac{n(n-1)}{4} $ edges.

I'd prefer hints to full answers, at least until I can reach the answer myself. Thanks for your help!

share|cite|improve this question
I believe Chris Godsil's answer to another question explains one direction: – Martin Sleziak Dec 2 '11 at 12:02
possible duplicate of Constructing self-complementary graphs – t.b. Dec 8 '11 at 7:10

2 Answers 2

Almost a spoiler hint:

When I had to prove this, I created solutions for cases n=4 and n=5 and generalized the individual solutions from those to sets of 4 (members of sets must form a complete graph between themselves) with extra node "in middle" for case where n=1(mod 4).

Since you've already created a solution for n=4, you are more than halfway there.

My professors proof only used two sets (and middle node for n=1(mod 4)), however my proof was deemed perfectly acceptable.

share|cite|improve this answer


Given a self complementary graph on $n$ vertices, try to construct a self-complementary graph on $n+4$ vertices.

Elaboration on the hint:

Given a self-complementary graph $G$ with $n$ vertices, add 4 more vertices which already form a 'Z' graph (the self-complementary graph for $n=4$). Connect the vertices of $G$ to some of four newly added vertices. Show that the new graph so formed, is a self-complementary graph on $n+4$ vertices.

Full answer:

Connect every vertex of $G$ to two of the vertices which are the farthest apart on the the n=4 graph (which is basically a path, and you connect all vertices of $G$ to the end points of that path).

This works even when $G$ has only one vertex.

share|cite|improve this answer
Thanks for your hint. I haven't managed to make any progress though – Anon Jul 5 '11 at 19:53
@Anon: I have elaborated on the hint... – Aryabhata Jul 5 '11 at 20:15
Can you show this proposition for the case of $n=1$? – SalmonKiller Nov 24 at 7:44
@SalmonKiller: I have added more explanation... – Aryabhata Nov 25 at 3:14

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.