Take the 2-minute tour ×
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|improve this question
    
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
add comment

2 Answers

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.

share|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.