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!
Best Answer
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.
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.