Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
See this answer – bof Dec 31 '15 at 21:35


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 '15 at 7:44
@SalmonKiller: I have added more explanation... – Aryabhata Nov 25 '15 at 3:14

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

Recursive constructions are very popular. The construction given in this answer (which I posted in a previous life) seems to be much less popular, but it is also quite simple. To wit:

Take a complete graph with vertex set $V$ and edge set $E={V\choose2}$. Let $\alpha$ be any permutation of $V$ in which the length of each cycle is a multiple of $4$, except for at most one $1$-cycle. (Of course, such permutations exist if and only if $|V|\equiv 0$ or $1\pmod 4$.)

Let $\beta$ be the permutation of $E$ induced by $\alpha$. Observe that $\beta$ contains only cycles of even length. Color the edges in each cycle alternately black and white. The graph $G$ consisting of the black edges is self-complementary. (The permutation $\alpha$ is an anti-automorphism of $G.$)

Example. To construct self-complementary graphs of order $5$, take $V=\{a,b,c,d,e\}$ and let $\alpha=(a\;b\;c\;d)(e)$ so that $\beta=(ab\;bc\;cd\;ad)(ac\;bd)(ae\;be\;\;ce\;de)\;$. If we choose the edges $ab,cd$ and $ac$ (i.e. "color them black") we get a $4$-point path $P_4$. Now we can choose the edges $be,de$ obtaining the self-complementary graph $C_5$, or else we can choose $ae,ce$ obtaining the other self-complementary graph of order $5$, the one that looks like the letter A.

This construction is completely general, in that every self-complementary graph can be obtained as an instance of this construction.

share|cite|improve this answer

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.