9
$\begingroup$

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!

  • 0
    I believe Chris Godsil's answer to another question explains one direction: http://math.stackexchange.com/a/86816/82972011-12-02
  • 2
    possible duplicate of [Constructing self-complementary graphs](http://math.stackexchange.com/questions/40745/constructing-self-complementary-graphs)2011-12-08
  • 0
    See [this answer](http://math.stackexchange.com/questions/40745/constructing-self-complementary-graphs/412930#412930)2015-12-31

3 Answers 3