# Existence of a self-complementary graph

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!

-
I believe Chris Godsil's answer to another question explains one direction: math.stackexchange.com/a/86816/8297 –  Martin Sleziak Dec 2 '11 at 12:02
possible duplicate of Constructing self-complementary graphs –  t.b. Dec 8 '11 at 7:10

Hint:

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.

-
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

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.

-